Bob is in love with Alice, a girl at his school. He always dreams of dating her, kissing her and playing weird games with her. But he is too shy to talk to Alice, so he decided to approach her through the internet first. He will start by adding her as a friend at LifeInvader (a very popular social network). But people often find it weird to accept you as a friend if they don’t know you, except when you have at least K friends in common with them. So Bob has to add some of Alice’s friends first. To add them, he has to add some of their friends too, and it goes on. He finds it futile to have friends he doesn’t really know at LifeInvader, so he wants to add the minimum additional friends. Help him know the minimum number of friends he has to add to be able to add Alice. It’s possible that Bob is friends with Alice already in LifeInvader, and is just messing with you. Input The first line contains T (T ≤ 200) — the number of test cases, after this line T test cases follows. Each test case starts with three integers N (2 ≤ N ≤ 20), M (0 ≤ M ≤ N∗(N−1)) and K (0 ≤ K ≤ N) — 2 the number of people in LifeInvader (including Bob and Alice), the number of current friendships and the minimum number of common friends you must have with someone to be able to add that person as a friend, correspondingly. Each person at LifeInvader is identified by a unique number between 1 and N. Bob is 1 and Alice is N. Then, M lines follow, each one with two numbers A and B (1 ≤ A,B ≤ N, A ̸= B), meaning that persons A and B are currently friends. Output For each test case print a line containing ‘Case #X: Y ’, where X is the case number, starting at 1, and Y is the minimum number of friends Bob has to add to be able to be friends with Alice, or ‘-1’ if that is impossible. Sample Input 3 321 12 23 761 12 23 34 45 56 67 432 12 24 34
2/2 Sample Output Case #1: 0 Case #2: 4 Case #3: -1