E. One-Way Reform

Codeforces

IDCF723E

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsdfs and similarflowsgraphsgreedy

English · Original

Chinese · Translation

Formal · Original

There are _n_ cities and _m_ two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads. The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to **maximize** the number of cities, for which the number of roads that begins in the city **equals** to the number of roads that ends in it. ## Input The first line contains a positive integer _t_ (1 ≤ _t_ ≤ 200) — the number of testsets in the input. Each of the testsets is given in the following way. The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 200, 0 ≤ _m_ ≤ _n_·(_n_ - 1) / 2) — the number of cities and the number of roads in Berland. The next _m_ lines contain the description of roads in Berland. Each line contains two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities. It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200. Pay attention that for **hacks**, you can only use tests consisting of **one testset**, so _t_ should be equal to one. ## Output For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it. In the next _m_ lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once. [samples]

伯兰国有 #cf_span[n] 座城市和 #cf_span[m] 条双向道路，每条道路连接两座城市。已知任意两座城市之间至多有一条道路，且不存在连接城市与自身的道路。可能存在某些城市之间无法仅通过这些道路相互到达。道路部长决定对伯兰国进行改革，将所有道路变为单向，即每条道路都赋予一个方向。部长希望*最大化*满足“从该城市出发的道路数量等于进入该城市的道路数量”的城市数量。输入的第一行包含一个正整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 200]) —— 输入数据中的测试用例数量。每个测试用例的格式如下：第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 200], #cf_span[0 ≤ m ≤ n·(n - 1) / 2]) —— 分别表示伯兰国的城市数和道路数。接下来的 #cf_span[m] 行描述了伯兰国的道路。每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n]) —— 表示该道路连接的两座城市。保证不存在自环和重边。可能存在某些城市对之间无法通过道路相互到达。保证所有测试用例中城市的总数不超过 #cf_span[200]。请注意，对于*黑客测试*，你只能使用仅包含*一个测试用例*的输入，因此 #cf_span[t] 必须等于 1。对于每个测试用例，输出满足“从该城市出发的道路数量等于进入该城市的道路数量”的城市最大可能数量。接下来的 #cf_span[m] 行输出每条道路的方向：每行先输出道路起点城市编号，再输出终点城市编号。如果有多个答案，输出任意一个即可。允许按任意顺序输出每组测试用例中的道路，每条道路必须且仅输出一次。 ## Input 输入的第一行包含一个正整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 200]) —— 输入数据中的测试用例数量。每个测试用例的第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 200], #cf_span[0 ≤ m ≤ n·(n - 1) / 2]) —— 分别表示伯兰国的城市数和道路数。接下来的 #cf_span[m] 行描述了伯兰国的道路，每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n]) —— 表示该道路连接的两座城市。保证不存在自环和重边。可能存在某些城市对之间无法通过道路相互到达。保证所有测试用例中城市的总数不超过 #cf_span[200]。请注意，对于*黑客测试*，你只能使用仅包含*一个测试用例*的输入，因此 #cf_span[t] 必须等于 1。 ## Output 对于每个测试用例，输出满足“从该城市出发的道路数量等于进入该城市的道路数量”的城市最大可能数量。接下来的 #cf_span[m] 行输出每条道路的方向：每行先输出道路起点城市编号，再输出终点城市编号。如果有多个答案，输出任意一个即可。允许按任意顺序输出每组测试用例中的道路，每条道路必须且仅输出一次。 [samples]

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. Let $ T = \{(n_k, E_k) \mid k \in \{1, \dots, t\}\} $ be the set of test cases, where for each $ k $: - $ n_k \in \mathbb{Z} $ is the number of cities. - $ E_k \subseteq \binom{[n_k]}{2} $ is the set of undirected edges (roads), with $ |E_k| = m_k $. Let $ G_k = ([n_k], E_k) $ be the undirected graph for test case $ k $. **Constraints** 1. $ 1 \le t \le 200 $ 2. For each $ k \in \{1, \dots, t\} $: - $ 1 \le n_k \le 200 $ - $ 0 \le m_k \le \frac{n_k(n_k - 1)}{2} $ - No self-loops or multiple edges in $ E_k $ 3. $ \sum_{k=1}^t n_k \le 200 $ **Objective** For each test case $ k $, assign an orientation to each edge $ \{u, v\} \in E_k $ to form a directed graph $ D_k = ([n_k], A_k) $, such that the number of vertices $ v \in [n_k] $ with $ \text{indeg}_{D_k}(v) = \text{outdeg}_{D_k}(v) $ is **maximized**. Output the maximum possible count of such vertices, and any orientation achieving it.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "E. One-Way Reform",
    "description": {
      "content": "There are _n_ cities and _m_ two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connect",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF723E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are _n_ cities and _m_ two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connect...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "伯兰国有 #cf_span[n] 座城市和 #cf_span[m] 条双向道路，每条道路连接两座城市。已知任意两座城市之间至多有一条道路，且不存在连接城市与自身的道路。可能存在某些城市之间无法仅通过这些道路相互到达。\n\n道路部长决定对伯兰国进行改革，将所有道路变为单向，即每条道路都赋予一个方向。部长希望*最大化*满足“从该城市出发的道路数量等于进入该城市的道路数量”的城市数量。\n\n输入的第一行包含...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ T = \\{(n_k, E_k) \\mid k \\in \\{1, \\dots, t\\}\\} $ be the set of test cases, where for each $ k $:  \n- $ n_k \\in \\mathbb{Z}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments