#include<bits/stdc++.h>
using namespace std;
bool isBipartite(int **G, int n)
{
// Create a color array to store colors
// assigned to all veritces. Vertex
// number is used as index in this array.
// The value ‘-1’ of colorArr[i]
// is used to indicate that no color
// is assigned to vertex ‘i’. The value 1
// is used to indicate first color
// is assigned and value 0 indicates
// second color is assigned.
int colorArr[n];
for (int i = 0; i < n; ++i)
colorArr[i] = -1;
int src;
// Assign first color to source
for(int i=0;i<n;i++)
{
if(colorArr[i]==-1)
{
src=i;
break;
}
}
// Create a queue (FIFO) of vertex
// numbers and enqueue source vertex
// for BFS traversal
queue <int> q;
q.push(src);
colorArr[src] =1;
// Run while there are vertices
// in queue (Similar to BFS)
while (!q.empty())
{
// Dequeue a vertex from queue ( Refer http://goo.gl/35oz8 )
int u = q.front();
q.pop();
// Return false if there is a self-loop
// Find all non-colored adjacent vertices
for (int v = 0; v < n; ++v)
{
// An edge from u to v exists and
// destination v is not colored
if (G[u][v] && colorArr[v] == -1)
{
// Assign alternate color to this adjacent v of u
colorArr[v] = 1 - colorArr[u];
q.push(v);
}
// An edge from u to v exists and destination
// v is colored with same color as u
else if (G[u][v] && colorArr[v] == colorArr[u])
return false;
}
}
// If we reach here, then all adjacent
// vertices can be colored with alternate color
return true;
}
int main()
{
int n;
cin>>n;
int *g=new int[n];
for(int i=0;i<n;i++)
{
g[i]=new int[n];
for(int j=0;j<n;j++)
{
g[i][j]=0;
}
}
for(int i=0;i<n;i++)
{
int f,s;
cin>>f>>s;
g[f][s]=1;
g[s][f]=1;
}
bool ans=isBipartite(g, n) ;
cout<<ans;
}