Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <map>
- #include <set>
- #include <sstream>
- #include <string>
- #include <iostream>
- #include <utility>
- #include <queue>
- #include <cmath>
- using namespace std;
- #define forn(i,n) for(int i=0;i<(n);++i)
- #define fornr(i,n) for(int i=(n)-1;i>=0;--i)
- #define forv(i,v) forn(i,(int)v.size())
- #define forvr(i,v) fornr(i,(int)v.size())
- #define mp make_pair
- #define pb push_back
- #define lng long long
- #define SQ(a) ((a)*(a))
- #define eps 1e-8
- #define VI vector<int>
- bool can[1000][1000];
- vector<int> grav[1000+100];
- bool was[1000+100];
- int s;
- int a[30000];
- int b[30000];
- void dfs(int v)
- {
- was[v]=true;
- can[s][v]=true;
- forv(i,grav[v])
- {
- if (!was[grav[v][i]])
- {
- dfs(grav[v][i]);
- }
- }
- }
- int val[30000];
- int main(int argc, char *argv[])
- {
- #ifdef __qwe__
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int n, m;
- cin >> n >> m;
- forn(i,m)
- {
- int u, v;
- scanf("%d%d", &u, &v);
- --u;--v;
- grav[u].pb(v);
- a[i]=u;
- b[i]=v;
- }
- forn(i,n)
- {
- s = i;
- memset(was,0,sizeof(was));
- dfs(s);
- }
- forn(i,m)
- {
- int x = a[i];
- int y = b[i];
- val[i]=0;
- forn(v,n)
- {
- if (can[x][v] && can[v][y])
- {
- ++val[i];
- continue;
- }
- if (can[y][v] && can[v][x])
- {
- ++val[i];
- continue;
- }
- if (can[y][v] && can[v][y])
- {
- ++val[i];
- continue;
- }
- if (can[x][v] && can[v][x])
- {
- ++val[i];
- continue;
- }
- }
- }
- int res = *max_element(val, val+m);
- printf("%d\n",res);
- int cnt=0;
- forn(i,m)if(val[i]==res)++cnt;
- printf("%d\n", cnt);
- forn(i,m)if(val[i]==res)printf("%d ",i+1);
- printf("\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement