1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
#include<cstring>
#define cls(a) memset(a,0,sizeof(a))
#define rg register
#define rep(i,x,y) for(rg int i=(x);i<=(y);++i)
#define per(i,x,y) for(rg int i=(x);i>=(y);--i)
using namespace std;
const int N=100+10,M=2000+10;
inline void dn(int&x,int y){if(y<x)x=y;}
int n,m,song[N][2],ps,nid[N<<1],nps;
struct Graph{
    int tot,head[N<<1],to[M],next[M],dfn[N<<1],lowlink[N<<1],clo,insta[N<<1],sta[N<<1],top;
    void clear(){tot=0;cls(head);}
    void ins(int a,int b){to[++tot]=b;next[tot]=head[a];head[a]=tot;}
    void dfs(int k,int pre){
        dfn[k]=lowlink[k]=++clo;insta[k]=1;sta[++top]=k;
        for(int p=head[k];p;p=next[p]){
            if(!dfn[to[p]])dfs(to[p],k),dn(lowlink[k],lowlink[to[p]]);
            else if(insta[to[p]])dn(lowlink[k],dfn[to[p]]);
        }
        if(lowlink[k]==dfn[k]){
            ++nps;
            while(sta[top]!=k){
                insta[sta[top]]=0;
                nid[sta[top--]]=nps;
            }nid[sta[top--]]=nps;
            insta[k]=0;
        }
    }
    bool check(){
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX