E. Desk Disorder

Codeforces

IDCF859E

Time2000ms

Memory256MB

Difficulty—

combinatoricsdfs and similardsugraphstrees

English · Original

Chinese · Translation

Formal · Original

A new set of desks just arrived, and it's about time! Things were getting quite cramped in the office. You've been put in charge of creating a new seating chart for the engineers. The desks are numbered, and you sent out a survey to the engineering team asking each engineer the number of the desk they currently sit at, and the number of the desk they would like to sit at (which may be the same as their current desk). Each engineer must either remain where they sit, or move to the desired seat they indicated in the survey. No two engineers currently sit at the same desk, nor may any two engineers sit at the same desk in the new seating arrangement. How many seating arrangements can you create that meet the specified requirements? The answer may be very large, so compute it modulo 1000000007 = 109 + 7. ## Input Input will begin with a line containing _N_ (1 ≤ _N_ ≤ 100000), the number of engineers. _N_ lines follow, each containing exactly two integers. The _i_\-th line contains the number of the current desk of the _i_\-th engineer and the number of the desk the _i_\-th engineer wants to move to. Desks are numbered from 1 to 2·_N_. It is guaranteed that no two engineers sit at the same desk. ## Output Print the number of possible assignments, modulo 1000000007 = 109 + 7. [samples] ## Note These are the possible assignments for the first example: * 1 5 3 7 * 1 2 3 7 * 5 2 3 7 * 1 5 7 3 * 1 2 7 3 * 5 2 7 3

一批新书桌刚刚到货，真是时候了！办公室里之前已经挤得不行了。你被委派负责为工程师们设计新的座位表。书桌都有编号，你向工程团队发放了一份调查问卷，询问每位工程师当前坐的书桌编号以及他们希望换到的书桌编号（可能与当前书桌相同）。每位工程师必须要么留在原位，要么移动到他们在问卷中指定的期望座位。当前没有两位工程师坐在同一张书桌上，新的座位安排中也不允许任何两位工程师坐在同一张书桌上。请问，有多少种满足上述要求的座位安排方式？答案可能非常大，请对 #cf_span[1000000007 = 109 + 7] 取模。输入的第一行包含一个整数 #cf_span[N]（#cf_span[1 ≤ N ≤ 100000]），表示工程师人数。接下来 #cf_span[N] 行，每行包含两个整数。第 #cf_span[i] 行包含第 #cf_span[i] 位工程师当前坐的书桌编号和他希望换到的书桌编号。书桌编号从 #cf_span[1] 到 #cf_span[2·N]。保证当前没有两位工程师坐在同一张书桌上。请输出满足条件的座位安排数量，对 #cf_span[1000000007 = 109 + 7] 取模。第一个示例的所有可能安排如下： ## Input 输入的第一行包含一个整数 #cf_span[N]（#cf_span[1 ≤ N ≤ 100000]），表示工程师人数。接下来 #cf_span[N] 行，每行包含两个整数。第 #cf_span[i] 行包含第 #cf_span[i] 位工程师当前坐的书桌编号和他希望换到的书桌编号。书桌编号从 #cf_span[1] 到 #cf_span[2·N]。保证当前没有两位工程师坐在同一张书桌上。 ## Output 请输出满足条件的座位安排数量，对 #cf_span[1000000007 = 109 + 7] 取模。 [samples] ## Note 第一个示例的所有可能安排如下： 1 5 3 7 1 2 3 7 5 2 3 7 1 5 7 3 1 2 7 3 5 2 7 3

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of engineers. For each engineer $ i \in \{1, \dots, N\} $, let $ (c_i, d_i) \in \{1, \dots, 2N\}^2 $ denote their current desk and desired desk, respectively. Let $ C = \{c_1, \dots, c_N\} $ be the set of current desks (all distinct). Let $ D = \{d_1, \dots, d_N\} $ be the set of desired desks. A valid assignment is a bijection $ f: \{1, \dots, N\} \to S $, where $ S \subseteq \{1, \dots, 2N\} $, $ |S| = N $, such that for all $ i $, $ f(i) \in \{c_i, d_i\} $, and $ f $ is injective (no two engineers assigned to same desk). **Constraints** 1. $ 1 \leq N \leq 100000 $ 2. $ c_i \ne c_j $ for all $ i \ne j $ 3. Desks are numbered from $ 1 $ to $ 2N $ **Objective** Compute the number of valid bijections $ f $ satisfying $ f(i) \in \{c_i, d_i\} $ for all $ i $, modulo $ 1000000007 $.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Desk Disorder",
    "description": {
      "content": "A new set of desks just arrived, and it's about time! Things were getting quite cramped in the office. You've been put in charge of creating a new seating chart for the engineers. The desks are number",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF859E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A new set of desks just arrived, and it's about time! Things were getting quite cramped in the office. You've been put in charge of creating a new seating chart for the engineers. The desks are number...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一批新书桌刚刚到货，真是时候了！办公室里之前已经挤得不行了。你被委派负责为工程师们设计新的座位表。书桌都有编号，你向工程团队发放了一份调查问卷，询问每位工程师当前坐的书桌编号以及他们希望换到的书桌编号（可能与当前书桌相同）。每位工程师必须要么留在原位，要么移动到他们在问卷中指定的期望座位。当前没有两位工程师坐在同一张书桌上，新的座位安排中也不允许任何两位工程师坐在同一张书桌上。\n\n请问，有多少种满...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of engineers.  \nFor each engineer $ i \\in \\{1, \\dots, N\\} $, let $ (c_i, d_i) \\in \\{1, \\dots, 2N\\}^2 $ denote their current desk and desired ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments