Problem Statement 
 You want to permute the numbers 0, 1, ..., N1 in certain order p_{0}, p_{1}, ..., p_{N1}. You are given a set of constraints of form "I J", where I and J are 0based indices of the positions in the permutation; these constraints tell you that p_{I} should be less than p_{J}. There is at most one constraint for each unordered pair of indices.
Find a permutation of the numbers which will satisfy as many constraints of the given list as possible. It is not guaranteed that a permutation which satisfies all constraints exists.
Implementation
Your code should implement a single method permute(int N, String[] constraints). Each element of constraints describes one constraint in form "I J", where I and J are 0based indices of the positions in the permutation.
You should return an array of N integers specifying the permutation p.
Scoring
The score is calculated as follows. For each test case, the raw score for it is the number of constraints which are satisfied by the returned permutation, divided by the total number of constraints. If the return is invalid (i.e. is not a permutation of numbers from 0 to N1), the score for that test case is 0.
The overall score will be the average of raw scores over all test cases, multiplied by 1,000,000.
Test Case Generation

The size of the permutation N is chosen between 10 and 1000, inclusive.

The number of constraints is chosen between N and N*(N1)/4, inclusive.

The probability of constraint generated incorrectly W is chosen between 0.1 and 0.3.

A random permutation of numbers 0, 1, ..., N1 q_{0}, q_{1}, ..., q_{N1} is generated. The constrains are created based on it. For each constraint two distinct indices I and J which haven't been used previously are chosen randomly. A correct constraint is generated based on the values of numbers q_{I} and q_{J} (if q_{I} is greater than q_{J} I and J are swapped). Finally, with probability W I and J are swapped.
Tools
An offline tester is available here. You can use it to test/debug your solution locally. You can also check its source code for exact implementation of test case generation and score calculation. That page also contains links to useful information and sample solutions in several languages. 

Definition 
 Class:  ConstrainedPermutation  Method:  permute  Parameters:  int, String[]  Returns:  int[]  Method signature:  int[] permute(int N, String[] constraints)  (be sure your method is public) 




Notes 
  The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes. 
  There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB. 
  The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here. 
  There are 10 example test cases and 100 full submission (provisional) test cases. There will be 500 test cases in the final testing. 
  The match is unrated. 

Examples 
0)  
 seed = 1
N = 10
K = 14
Incorrect constraint probability = 0.2553452771879665
Constraints:
7 4
8 2
8 5
1 9
6 1
2 7
3 9
0 9
8 3
9 5
7 5
8 9
0 6
8 6
 

1)  
 seed = 2
N = 30
K = 108
Incorrect constraint probability = 0.23112787015918956
Constraints:
2 8
0 20
26 7
24 0
11 18
0 29
27 11
18 19
18 27
19 10
23 18
1 20
16 9
6 28
25 11
7 21
17 13
3 21
4 10
11 7
29 24
6 23
24 14
27 16
23 22
21 4
11 28
13 27
4 1
23 29
12 28
11 14
1 28
20 27
22 0
19 17
16 8
19 2
22 29
9 23
14 27
24 6
16 18
29 28
14 0
0 12
19 20
17 3
13 24
2 25
25 26
29 11
11 26
24 26
3 13
16 17
5 4
7 1
12 9
6 18
19 28
6 4
5 28
14 17
19 11
15 23
15 25
19 9
0 25
16 26
3 9
20 14
24 22
8 23
16 23
20 3
2 3
3 23
7 23
29 20
29 10
16 7
9 4
2 1
0 10
2 6
21 18
5 25
25 16
5 17
24 16
5 18
23 24
23 25
13 15
14 5
17 18
14 25
3 24
19 23
14 26
15 14
19 12
7 3
25 1
16 4
12 27
0 17
 

2)  
 seed = 3
N = 1000
K = 203510
 

3)  
 seed = 4
N = 761
K = 81502
 

4)  
 seed = 5
N = 852
K = 124835
 

5)  
 seed = 6
N = 586
K = 5014
 

6)  
 seed = 7
N = 506
K = 37496
 

7)  
 seed = 8
N = 289
K = 17489
 

8)  
 seed = 9
N = 164
K = 2608
 

9)  
 seed = 10
N = 620
K = 80648
 
