D. Subway

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A subway scheme, classic for all Berland cities is represented by a set of n stations connected by n passages, each of which connects exactly two stations and does not pass through any others. Besides, in the classic scheme one can get from any station to any other one along the passages. The passages can be used to move in both directions. Between each pair of stations there is no more than one passage.

Berland mathematicians have recently proved a theorem that states that any classic scheme has a ringroad. There can be only one ringroad. In other words, in any classic scheme one can find the only scheme consisting of stations (where any two neighbouring ones are linked by a passage) and this cycle doesn't contain any station more than once.

This invention had a powerful social impact as now the stations could be compared according to their distance from the ringroad. For example, a citizen could say "I live in three passages from the ringroad" and another one could reply "you loser, I live in one passage from the ringroad". The Internet soon got filled with applications that promised to count the distance from the station to the ringroad (send a text message to a short number...).

The Berland government decided to put an end to these disturbances and start to control the situation. You are requested to write a program that can determine the remoteness from the ringroad for each station by the city subway scheme.

Input

The first line contains an integer n (3 ≤ n ≤ 3000), n is the number of stations (and trains at the same time) in the subway scheme. Then n lines contain descriptions of the trains, one per line. Each line contains a pair of integers xi, yi (1 ≤ xi, yi ≤ n) and represents the presence of a passage from station xi to station yi. The stations are numbered from 1 to n in an arbitrary order. It is guaranteed thatxi ≠ yi and that no pair of stations contain more than one passage. The passages can be used to travel both ways. It is guaranteed that the given description represents a classic subway scheme.

Output

Print n numbers. Separate the numbers by spaces, the i-th one should be equal to the distance of the i-th station from the ringroad. For the ringroad stations print number 0.

Sample test(s)

input

4
1 3
4 3
4 2
1 2

output

0 0 0 0 

input

6
1 2
3 4
6 4
2 3
1 3
3 5

output

0 0 0 1 1 2 

DISCUSSION ON THE IMPLEMENTATION

 The question asks us to find a the nodes in the circle in the given graph and then find the distance of all other nodes from the nodes present in the circle.

This question can be divided in two steps

(1) finding the circle 

As the numnber of circle in only 1. an O(n) dfs yields the nodes in the circle.

Starting with any node, we call dfs and mark the visited node as 2(attention we need three states of visited array 0,1 and 2 , 0 for an unvisited node, 1 for a node not a part of circle and 2 for a node that is going to be revisited 2wice.) We see if visited[i]==0 we mark the parent for the node and call dfs recursively for its children. If any time visited[root]=2 is called , we know that this node is being revisited. so we backtrack from the present parent of the revisited node to the node itself through its parent array to mark the fact that these nodes form a circle.

An important observation is to set the visted[node] to 1 after all the pending calls are done.(That means the node is no more to be considered).

Step 2

It is simple BFS (it is preferable we start from a node of the ring), 

The condition for pushing it is if(d[visiting node]>d[parent]+1) then update the distance and revisit the node. If the node is in the circle simply set it to 0.

           ***** The code is *******

#include<iostream>

#include<stdio.h>

#include<queue>

#include<stack>

#include<list>

using namespace std;

list<int> arr[3010];

int visited[3020];

int cycles[3020];

int dist[3020];

int parent[3020];

void distance(int root)

{

dist[root]=0;

queue<int> q;

q.push(root);

   int node;

   while(!q.empty())

   {

    node=q.front();

   // cout<<"node "<<node<< endl;

    q.pop();

    list<int>:: iterator it;

    {

      for(it=arr[node].begin();it!=arr[node].end();it++)

      {

         if(dist[*it]>dist[node]+1)

        {

          if(cycles[*it]==1)

          dist[*it]=0;

 else

 dist[*it]=1+dist[node];

        q.push(*it);

        }

      }

    }

   }

}

void dfs(int root , int par)

{

if(visited[root]==0)

{

visited[root]=2;

parent[root]=par;

list<int> ::iterator it;

for(it=arr[root].begin();it!=arr[root].end();it++)

{

if(*it!=par)

{

dfs(*it,root);

}

}

visited[root]=1;}

if(visited[root]==2)

{

// cout<<"here "<<root<<endl;

int node=par;

while(node!=root)

{

// cout<<"node   "<<node<<endl;

cycles[node]=1;

node=parent[node];

}

cycles[root]=1;

}

}

void fill(int filler[],int val, int lim)

{

for(int i=0;i<=lim+2;i++)

{

filler[i]=val;

}

}

int main()

{

int n;

cin>>n;

int a,b;

for(int i=1;i<=n;i++)

{

cin>>a>>b;

arr[a].push_back(b);

arr[b].push_back(a);

}

fill(visited,0,n+2);

fill(dist,1000000,n+2);

fill(cycles,-1,n+2);

fill(parent,0,n+2);

dfs(1,-1);

// cout<<"Exiting "<<endl;

for(int i=1;i<=n;i++)

{

if(cycles[i]==1)

{  

// cout<<"bfs call using "<<i<<endl;

distance(i);

break;

}

}

for(int i=1;i<=n;i++)

{

cout<<dist[i]<<" ";

}

cout<<endl;

return 0;

}

   **** The code ends here****