I. Two friends

Codeforces

IDCF10049I

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

It is not so easy to meet with your friend in the forest when you are both lost. You might ask how that would happen? Well, imagine, you are going with your friend, you are quite fast and your friend is slow. As there is a big fog, you turn around and you can't find your friend. There is quite a shock, of course. But it is interesting to know what the expected time to meet with your friend would be, if you just waited in your place or went to any neighbouring place completely at random (with the same probability). We assume that your friend would do the same. For example, if you are at place which has 3 neighbouring places, you would wait with the probability equal to 0.25 and you go to any of the 3 places with probability equal to 0.25. Assume, that you are doing the same operation each moment of time (as well as your friend). You meet with your friend at the i-th place, if you and your friend happen to be at the same i-th place for the first time after some number of described steps. The place is neighbouring to the given place if they are connected by a path. The first line contains the number of test cases T (1 ≤ T ≤ 50). In the first line of every test case there are two integers n (1 ≤ n ≤ 15) and m (0 ≤ m ≤ n·(n - 1) / 2) - the number of places in the forest and the number of paths. Two places have at most one path between them. In the following m lines of every test case there two numbers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - the places connected by an undirected i-th path. In the last line of every test case there are two integers a and b (1 ≤ a, b ≤ n) - the first friend's initial place and the second friend's initial place. *Note*: the forest is not necessarily connected. For each test case output one line containing “_Case #tc: exp1 exp2 ... expn_” where tc is the number of the test case (starting from 1) and expi shows the expected numbers of steps to meet at the i-th place. The answer will be considered correct if the absolute or relative error does not exceed *10 - 7* compared with the judge's answer. If it is not possible to meet at the i-th place, print "N/A" as its expectation. ## Input The first line contains the number of test cases T (1 ≤ T ≤ 50). In the first line of every test case there are two integers n (1 ≤ n ≤ 15) and m (0 ≤ m ≤ n·(n - 1) / 2) - the number of places in the forest and the number of paths. Two places have at most one path between them.In the following m lines of every test case there two numbers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - the places connected by an undirected i-th path.In the last line of every test case there are two integers a and b (1 ≤ a, b ≤ n) - the first friend's initial place and the second friend's initial place.*Note*: the forest is not necessarily connected. ## Output For each test case output one line containing “_Case #tc: exp1 exp2 ... expn_” where tc is the number of the test case (starting from 1) and expi shows the expected numbers of steps to meet at the i-th place. The answer will be considered correct if the absolute or relative error does not exceed *10 - 7* compared with the judge's answer. If it is not possible to meet at the i-th place, print "N/A" as its expectation. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases, with $ 1 \leq T \leq 100 $. For each test case $ k \in \{1, \dots, T\} $, let $ s_k $ be a string representing a recurring decimal of length $ \leq 15 $, of the form: $ s_k = \text{non-repeating part} + \text{repeating part enclosed in parentheses} $, where the non-repeating part may be empty, and the repeating part is non-empty. Let $ x_k \in \mathbb{Q}^+ $ be the rational number represented by $ s_k $. **Constraints** 1. $ 1 \leq T \leq 100 $ 2. Each $ s_k $ is a valid recurring decimal representation of a positive fraction. 3. Length of $ s_k \leq 15 $. 4. The repeating part is always enclosed in parentheses and non-empty. 5. The decimal contains only digits and exactly one pair of parentheses. **Objective** For each test case $ k $, find the unique irreducible fraction $ \frac{a_k}{b_k} \in \mathbb{Q}^+ $ such that $ \frac{a_k}{b_k} = x_k $, where $ \gcd(a_k, b_k) = 1 $.

API Response (JSON)

{
  "problem": {
    "name": "I. Two friends",
    "description": {
      "content": "It is not so easy to meet with your friend in the forest when you are both lost. You might ask how that would happen? Well, imagine, you are going with your friend, you are quite fast and your friend ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10049I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "It is not so easy to meet with your friend in the forest when you are both lost. You might ask how that would happen? Well, imagine, you are going with your friend, you are quite fast and your friend ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases, with $ 1 \\leq T \\leq 100 $.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ s_k $ be a string representing a recurring dec...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments