#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long inf=1e18;
long long n,m,dh[100069],dsu[100069],an[100069],dp[100069];
pair<long long,long long> ed[100069];
vector<long long> al[100069];
bitset<100069> vtd,vtd2;
long long fd(long long x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
void dfs(long long x)
{
long long i,sz=al[x].size(),l;
vtd[x]=1;
vtd2[x]=1;
an[x]=0;
for(i=0;i<sz;i++)
{
l=al[x][i];
if(!vtd[l])
{
dh[l]=dh[x]+1;
dfs(l);
}
if(vtd2[l])
{
if(dh[l]>dh[an[x]])
{
an[x]=l;
}
}
else if(an[l]&&vtd2[an[l]])
{
if(dh[an[l]]>dh[an[x]])
{
an[x]=an[l];
}
}
}
vtd2[x]=0;
}
void dfs2(long long x)
{
long long i,sz=al[x].size(),l;
vtd[x]=1;
vtd2[x]=1;
dp[x]=0;
for(i=0;i<sz;i++)
{
l=al[x][i];
if(!vtd[l])
{
dfs2(l);
}
if(!vtd2[l])
{
if(dp[x]==2&&dp[l]==2)
{
dp[x]=2;
}
else if(!an[l]||!vtd2[an[l]]||an[l]==x)
{
dp[x]=min(dp[x]+dp[l],2ll);
}
}
}
vtd2[x]=0;
dp[x]=max(dp[x],(long long)!!an[x]);
}
variant<bool,vector<int>> find_journey(int on,int om,vector<int> ka,vector<int> la)
{
long long i,k,l;
variant<bool,vector<int>> sq;
n=on;
m=om;
for(i=1;i<=m;i++)
{
k=ka[i-1]+1;
l=la[i-1]+1;
ed[i]={k,l};
al[k].push_back(l);
}
dh[0]=-inf;
dfs(1);
vtd.reset();
dfs2(1);
return dp[1]==2;
}
