DISGRAPH - Disconnected country


Cities of the ancient country GRAPH connected by two-way (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.

DISGRAPH


hide comments
hossam_yehia: 2019-04-02 23:43:08

Weak test cases

this case

7
1 2 3
0
0 4 6
0 4
2 3 5
4 6
2 5

should output 1
my code output 2
and got accepted

another case :

22
1 2 8 15
0 2 3
0 1 3
1 2 4
3 5 6
4 6 7
4 5 7
5 6
0 9 15 16
8 10 16 17
9 11 17 18
10 12 19 18
11 13 19 20
12 14 20 21
13 21
0 8
8 9
9 10
10 11
11 12
12 13
13 14

should output 1
my code output 2
and got accepted

<== [Reply] Thank you for solving my problem and comments.

Last edit: 2019-04-04 20:30:32
Rohit Agarwal: 2018-10-28 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)

Edit: I solved it, the problem was arising because my default minm was set to 10M, I changed it to INT_MAX and it works but with 1400 vertices, we can have around 1960000 edges. So, the answer could be at max that so, setting to 10M sounds safe but it wasn't. :(

Last edit: 2018-10-29 15:43:26
Rohit Agarwal: 2018-10-23 02:29:19

test case 6 fails :/ @julkas : Can you please provide me a test-case that may fail for my last solution? Thanks!

<== [Reply] Your solution gives answer 0 for input example. Check your algo implementation. You can also try similar problem ADABANKET first.

Last edit: 2018-10-25 10:00:41
julkas: 2018-05-16 13:55:12

@devilwolverine My pleasure. Best regards.

Vipul Srivastava: 2018-05-16 10:30:28

@julkas Thanks a lot, your test case helped me get AC.

Also I found the problem to be quite interesting and I think it should be in classical section.

Last edit: 2018-05-16 13:01:59
julkas: 2018-05-14 12:48:43

@xilinx OK. I know this problem. Thank you for comment.

Last edit: 2018-06-24 16:29:41
[Rampage] Blue.Mary: 2018-05-14 12:14:15

A same problem already exists at SPOJ: http://www.spoj.com/problems/ADABANKET/

Edit: I've used the same program of that problem (IO format modified) to get AC here.

Last edit: 2018-05-14 17:12:14

Added by:julkas
Date:2018-05-05
Time limit:1s-11s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Inspired by ADABANKET