#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int kMaxN = 55 ;
struct node
{
	int v , nxt ;
}edge[kMaxN * kMaxN] ;
int low[kMaxN] , dfn[kMaxN] , head[kMaxN] ;
int n , m , res , tim , cnt = 1 ;
void add_edge(int u , int v)
{
	edge[++cnt] = {v , head[u]} ;
	head[u] = cnt ;
} 
void tanjan(int u , int fa)
{
	dfn[u] = low[u] = ++tim ;
	for( int i = head[u] ; i ; i = edge[i].nxt )
	{
		int v = edge[i].v ;
		if(v == fa) continue ;
		if(dfn[v] == 0)
		{
			tanjan(v , u) ;
			low[u] = min(low[u] , low[v]) ;
			if(low[v] > dfn[u]) res++ ;
		}
		else 
		{
			low[u] = min(low[u] , dfn[v]) ;
		}
	}
}
void solve()
{
	cin >> n >> m ;
	for( int i = 1 ; i <= m ; i++ )
	{
		int u , v ;
		cin >> u >> v ;
		add_edge(u , v) ;
		add_edge(v , u) ;
	}
	for( int i = 1 ; i <= n ; i++ )
	{
		if(dfn[i] == 0) tanjan(i , -1) ;
	}
	if(tim != n) cout << 0 ;
	else cout << res ;
}
signed main()
{
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
//	freopen("T1.in" , "r" , stdin) ;
//	freopen("T1.out" , "w" , stdout) ;
	int t = 1 ;
//	cin >> t ;
	while(t--) solve() ;
	return 0 ;
}

#include <bits/stdc++.h>
#define int long long
using namespace std ;
const int kMaxN = 5e4 + 10, Mod = 1e9;
int n , m , dfn[kMaxN] , low[kMaxN] , col[kMaxN] , scc , tim , in[kMaxN] , cnt[kMaxN] , dp[kMaxN] ;
bool vis[kMaxN] , vis1[kMaxN] , vis2[kMaxN] ;
vector<int> nbr[kMaxN] , re_nbr[kMaxN] ;
stack<int> stk ;
void tarjan(int u) 
{
	vis[u] = 1 ;
	stk.push(u) ;
	dfn[u] = low[u] = ++tim ;
	for( int v : nbr[u] ) 
	{
		if (!dfn[v]) 
		{
			tarjan(v) ;
			low[u] = min(low[u] , low[v]) ;
		} 
		else if (vis[v]) 
		{
			low[u] = min(low[u] , dfn[v]) ;
		}
	}
	if (dfn[u] == low[u]) 
	{
		scc++ ;
		while (!stk.empty()) 
		{
			col[stk.top()] = scc ;
			vis[stk.top()] = 0 ;
			if (stk.top() == u) 
			{
				stk.pop() ;
				break ;
			}
			stk.pop() ;
		}
	}
}
void bfs1() 
{
	queue<int> q ;
	vis1[1] = 1 ;
	q.push(1) ;
	while (!q.empty())
	{
		int u = q.front() ;
		q.pop() ;
		for( int v : nbr[u] ) 
		{
			if (!vis1[v]) 
			{
				vis1[v] = 1 ;
				q.push(v) ;
			}
			in[v]++ ;
		}
	}
}
void bfs2() 
{
	queue<int> q ;
	vis2[2] = 1 ;
	q.push(2) ;
	while (!q.empty()) 
	{
		int u = q.front() ;
		q.pop() ;
		for( int v : re_nbr[u] ) 
		{
			if (!vis2[v]) 
			{
				vis2[v] = 1 ;
				q.push(v) ;
			}
		}
	}
}
void topo() 
{
	queue<int> q ;
	dp[1] = 1 ;
	q.push(1) ;
	while (!q.empty()) 
	{
		int u = q.front() ;
		q.pop() ;
		for( int v : nbr[u] ) 
		{
			if (vis2[v]) 
			{
				long long sum = dp[v] + dp[u] ;
				sum %= Mod ;
				dp[v] = sum;
				in[v]-- ;
				if (!in[v]) q.push(v) ;
			}
		}
	}
}
signed main() {
//	freopen("T2.in", "r", stdin);
//	freopen("T2.out", "w", stdout);
	cin >> n >> m ;
	for( int i = 1 ; i <= m ; i++ ) 
	{
		int u , v ;
		cin >> u >> v ;
		nbr[u].push_back(v) ; 
		re_nbr[v].push_back(u) ;
	}
	for( int i = 1 ; i <= n ; i++ ) 
	{
		if (!dfn[i]) tarjan(i) ;
	}
	for( int i = 1 ; i <= n ; i++ ) 
	{
		cnt[col[i]]++ ;
	}
	bfs1() ;
	bfs2() ;
	for( int i = 1 ; i <= n ; i++ ) 
	{
		if (vis1[i] && vis2[i] && cnt[col[i]] != 1) 
		{
			cout << "inf" ;
			return 0 ;
		}
	}
	topo() ;
	cout << dp[2] ;
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int kMaxN = 2e5 + 5 ;
struct Edge 
{
	int v , nxt , w ;
}edge[kMaxN * 2] ;
int low[kMaxN] , dfn[kMaxN] , ans[kMaxN] , dis[2][kMaxN] , head[kMaxN] , u[kMaxN] , v[kMaxN] , w[kMaxN] ;
bool vis[kMaxN] , bri[kMaxN * 2] ;
int n , m , res , tim , cnt ;
void add_edge(int u , int v , int w)
{
	edge[++cnt] = {v , head[u] , w} ;
	head[u] = cnt ;
} 
struct node
{
	int id ;
	int w ;
	bool operator < (const node & B) const
	{
		return w > B.w ;
	}
};
priority_queue<node> Q ;
void dij(int s , int k)
{
	fill(vis + 1 , vis + n + 1 , 0) ;
	dis[k][s] = 0 ;
	Q.push({s , 0}) ;
	while(!Q.empty())
	{
		int u = Q.top().id ;
		Q.pop() ;
		if(vis[u]) continue ;
		vis[u] = 1 ;
		for( int i = head[u] ; i ; i = edge[i].nxt )
		{
			int v = edge[i].v ;
			if(dis[k][v] > dis[k][u] + edge[i].w)
			{
				dis[k][v] = dis[k][u] + edge[i].w ;
				Q.push({v , dis[k][v]}) ;
			}
		}
	}
}
void tanjan(int u , int fa)
{
	dfn[u] = low[u] = ++tim ;
	for( int i = head[u] ; i ; i = edge[i].nxt )
	{
		int v = edge[i].v ;
		if(dfn[v] == 0)
		{
			tanjan(v , i ^ 1) ;
			low[u] = min(low[u] , low[v]) ;
			if(low[v] > dfn[u]) 
			{
				bri[i] = bri[i ^ 1] = 1 ;
			}
		}
		else if(i != fa)
		{
			low[u] = min(low[u] , dfn[v]) ;
		}
	}
}
void solve()
{
	cin >> n >> m ;
	for( int i = 1 ; i <= m ; i++ )
	{
		cin >> u[i] >> v[i] >> w[i] ;
		add_edge(u[i] , v[i] , w[i]) ;
		add_edge(v[i] , u[i] , w[i]) ;
	}
	memset(dis , 0x3f , sizeof dis) ;
	dij(1 , 0) ;
	dij(n , 1) ;
	fill(head + 1 , head + n + 1 , 0) ;
	cnt = 1 ;
	for( int i = 1 ; i <= m ; i++ )
	{
		if((dis[0][u[i]] + dis[1][v[i]] + w[i] == dis[0][n]) || (dis[0][v[i]] + dis[1][u[i]] + w[i] == dis[0][n])) 
		{
			vis[i] = 1 ;
			add_edge(u[i] , v[i] , w[i]) ;
			add_edge(v[i] , u[i] , w[i]) ;
      ans[i] = cnt ;
		}
	}
	for( int i = 1 ; i <= n ; i++ )
	{
		if(dfn[i] == 0)
		{
			tanjan(i , 0) ;
		}
	}
	for( int i = 1 ; i <= m ; i++ )
	{
		if(ans[i] == 0)
		{
			cout << "No\n" ;
		}
		else
		{
			if(bri[ans[i]])
			{
				cout << "Yes\n" ;
			}
			else
			{
				cout << "No\n" ;
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
//	freopen("T3.in" , "r" , stdin) ;
//	freopen("T3.out" , "w" , stdout) ;
	int t = 1 ;
//	cin >> t ;
	while(t--) solve() ;
	return 0 ;
}