04-24-2018, 11:55 PM

Problem:

There are n people who call themselves friends. However, you can't trust people blindly these days! Not each of these people trusts all the other people. The good thing is, still there are some pairs of people who trust each other and consider each other as true friends. Also, each person has a best friend. Note that a best friend is also a true friend.

These relations are symmetric. Formally, person A has several true friends who also consider A as a true friend. Person A has exactly one best friend, B, and A is also the best friend of B.

Each person has a secret. Those n secrets are written on n pieces of papers. Those papers are sealed inside n envelopes. The name of the person, whose secret is written on the paper inside an envelop, is written on the envelope. These n envelopes are distributed among the n people. At each step, one person exchanges the envelope (without opening it) he/she is holding with one of his/her true friends. Your job is to determine the minimum number of steps (exchanges) required to end up at an arrangement where secret about each person reaches the hand of that person or the best friend of that person, i.e. finally after these exchanges when the envelopes are opened, the secrets of a particular person is either seen by himself or his best friend.

Output:

For each test case, print "Case i: ", and then the answer, where i is the testcase number, 1-indexed. The answer should be the required number of steps. If it's not possible to make all the secrets (envelopes) reach in safe hands, the answer should be "IMPOSSIBLE" (without quotes)

Constraints:

Input:

2

4

2 3 4 1

3 4 1 2

1

2 3

4

2 1 4 3

3 4 1 2

0

Output:

Case 1: 4

Case 2: IMPOSSIBLE

There are n people who call themselves friends. However, you can't trust people blindly these days! Not each of these people trusts all the other people. The good thing is, still there are some pairs of people who trust each other and consider each other as true friends. Also, each person has a best friend. Note that a best friend is also a true friend.

These relations are symmetric. Formally, person A has several true friends who also consider A as a true friend. Person A has exactly one best friend, B, and A is also the best friend of B.

Each person has a secret. Those n secrets are written on n pieces of papers. Those papers are sealed inside n envelopes. The name of the person, whose secret is written on the paper inside an envelop, is written on the envelope. These n envelopes are distributed among the n people. At each step, one person exchanges the envelope (without opening it) he/she is holding with one of his/her true friends. Your job is to determine the minimum number of steps (exchanges) required to end up at an arrangement where secret about each person reaches the hand of that person or the best friend of that person, i.e. finally after these exchanges when the envelopes are opened, the secrets of a particular person is either seen by himself or his best friend.

Output:

For each test case, print "Case i: ", and then the answer, where i is the testcase number, 1-indexed. The answer should be the required number of steps. If it's not possible to make all the secrets (envelopes) reach in safe hands, the answer should be "IMPOSSIBLE" (without quotes)

Constraints:

- 1 ≤ T ≤ 10

- 1 ≤ n ≤ 10

- n will be even

- 0 ≤ m ≤ 10

- 1 ≤ ei, fi, ai, bi ≤ n

- The answer, if it exists, will be less than or equal to 18.

Input:

2

4

2 3 4 1

3 4 1 2

1

2 3

4

2 1 4 3

3 4 1 2

0

Output:

Case 1: 4

Case 2: IMPOSSIBLE