Stepping Up

Problem code: STEPUP

All submissions for this problem are available.

Statement

Given a directed graph G with N vertices and M edges. For each vertex u, you must assign positive integer F(u) such that:

  1. For each edge e from a to b, F(b) > F(a)
  2. The maximum value m = max( F(u) ) is minimized

Output the maximum value m. If no such assignment is possible output "IMPOSSIBLE" (quotes for clarity).

INPUT FORMAT

First line of input contains a number t, the number of test cases.
Each test case contain starts with two space seperated integers N and M, denoting the number of vertices and the number of edges in the graph respectively.
Each of the following M lines contain two space seperated integers a b denoting an edge from vertex a to vertex b.
There can be multiple edges between two vertices a and b.

OUTPUT FORMAT

For each testcase output the maximum value m or "IMPOSSIBLE" if no assignment is possible.

SAMPLE INPUT

2
2 2
1 2
2 1
3 2
1 2
1 3

SAMPLE OUTPUT

IMPOSSIBLE
2

CONSTRAINTS

t <= 20
N <= 10000
M <= 20000
1 <= a,b <= N

EXPLANATION

A feasible assignment for the second testcase is: 

Vertex	             Number
1			1
2			2
3			2

So the maximum value is 2
Date: 2010-09-10
Time limit: 2s
Source limit: 50000
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS


Comments

For the input: 14 41 21 33 44

thought @ 24 Sep 2010 11:10 PM

For the input:

1
4 4
1 2
1 3
3 4
4 2

The solution of user with id "algogeeks" returns "IMPOSSIBLE",

while the expected answer is 4. They have AC on this!!

@Admin : I think there was

damn @ 25 Sep 2010 01:17 AM

@Admin : I think there was incomplete data-set used in this question.

I tested the code of team knighttemplars with the following dataset

1

3 2

2 3

1 2

And these codes return output as 2, but the answer should be 3

Also for algogeeks this test-set  :

1

3 3

1 2

1 3

2 3

It returns 2 but answer should be 3

Please Check the codes or better test cases

 

For the input: 17 91 21 31 42

three_cube @ 25 Sep 2010 01:12 PM

For the input:

1
7 9
1 2
1 3
1 4
2 4
2 5
3 7
4 3
6 5
7 6

The solution of user with id "algogeeks" returns "IMPOSSIBLE",

while the expected answer is 6.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions