DISGRAPH  Disconnected country
Cities of the ancient country GRAPH connected by twoway (bidirectional) roads so that from any city you can get to any other city. The Sultan wants to destroy some roads and divide the country into two separate (disconnected) areas, so that from the city of one area it was impossible to get to the city of another area. You are the Minister of transportation and your task is to minimize the number of roads that need to be destroyed. You have a lot of time and the Sultan hopes :) that you will solve this task.
Input
The first line of input will contain one integer number 8 ≤ N ≤ 1400, number of cities in GRAPH. Follow N lines. Each line represents cities (direct neighbors) connected to the city number i (cities numbering is zero based) by one road. There will be 7 input files.
Output
One integer number. The minimum number of roads that need to be destroyed.
Example
Input: 8 1 2 0 2 3 0 1 3 1 2 4 3 5 6 4 6 7 4 5 7 5 6
Output: 1
Example explanation
Destroy only one road from the third city to the fourth city and Sultan will be happy.
hide comments
hossam_yehia:
20190402 23:43:08
Weak test cases


Rohit Agarwal:
20181028 22:07:44
@Julkas: Thanks for the help and my code fails in ADBANKET too but I don't seem to understand where. :/ Are there any special kind of graph I should look out for? I don't seem to find my mistake. I even wrote a brute force O(V . V^2 E) algorithm which receives a WA (one of my first few submissions)


Rohit Agarwal:
20181023 02:29:19
test case 6 fails :/ @julkas : Can you please provide me a testcase that may fail for my last solution? Thanks!


julkas:
20180516 13:55:12
@devilwolverine My pleasure. Best regards. 

Vipul Srivastava:
20180516 10:30:28
@julkas Thanks a lot, your test case helped me get AC.


julkas:
20180514 12:48:43
@xilinx OK. I know this problem. Thank you for comment. Last edit: 20180624 16:29:41 

[Rampage] Blue.Mary:
20180514 12:14:15
A same problem already exists at SPOJ: http://www.spoj.com/problems/ADABANKET/

Added by:  julkas 
Date:  20180505 
Time limit:  1s11s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Inspired by ADABANKET 