I. Ehab The Baby Learned Graphs

Codeforces

IDCF10288I

Time1000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

After learning to walk, Ehab the baby started learning graph theory. He never found the definition of the $x o r$ of 2 graphs, so he decided that the $x o r$ of 2 undirected graphs having the same number of vertices is defined as follows: the resulting graph has the same number of vertices and an edge exists in it if and only if it exists in exactly one of the two input graphs. Now, Ehab made a new graph out of.. Well.. His cubes. The graph is undirected and connected, and it has $n$ vertices and $m$ edges. Ehab asked his "babysitter" Laggy to find at most $n + m$ trees consisting of $n$ nodes such that: Laggy, of course, didn't solve it, so it's your turn. Can you solve it? The first line contains a single integer integer $n$ ($2 <= n <= 100$) — the number of vertices in the graph. The next $n$ lines contain $n$ integers each. If the $j_{t h}$ number in the $i_{t h}$ line is 1, then vertices $i$ and $j$ are connected by an edge. If it's 0, then they're not. It's guaranteed that the graph is connected and doesn't have self-loops. If it's impossible to solve the problem for this case, print one line containing "-1". Otherwise: On the first line, print the number of trees $t$ you wish to use. It should be at most $n + m$. On the next $t$ output blocks, you should print the trees. Each block consists of $n -1$ lines containing 2 integers $u$ and $v$ ($1 <= u, v <= n$) which mean that there's an edge between nodes $u$ and $v$ in this tree. Each block must describe a tree. If there are multiple solutions, print any of them. You can print the edges of a tree in any order. ## Input The first line contains a single integer integer $n$ ($2 <= n <= 100$) — the number of vertices in the graph.The next $n$ lines contain $n$ integers each. If the $j_{t h}$ number in the $i_{t h}$ line is 1, then vertices $i$ and $j$ are connected by an edge. If it's 0, then they're not.It's guaranteed that the graph is connected and doesn't have self-loops. ## Output If it's impossible to solve the problem for this case, print one line containing "-1". Otherwise:On the first line, print the number of trees $t$ you wish to use. It should be at most $n + m$.On the next $t$ output blocks, you should print the trees. Each block consists of $n -1$ lines containing 2 integers $u$ and $v$ ($1 <= u, v <= n$) which mean that there's an edge between nodes $u$ and $v$ in this tree. Each block must describe a tree.If there are multiple solutions, print any of them. You can print the edges of a tree in any order. [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $. Define the graph $ K_{n,m} $ as the complete bipartite graph with bipartition $ (U, V) $, where $ |U| = n $, $ |V| = m $, and every vertex in $ U $ is connected to every vertex in $ V $, with no edges within $ U $ or within $ V $. **Random Walk Model** A random walk begins at a uniformly random vertex in $ U \cup V $. At each step, the walk moves uniformly at random to a neighbor. The walk stops when it first visits a vertex that has been visited before. Let $ T $ be the stopping time (number of steps until first revisit to any vertex). **Constraints** $ 1 \leq n, m \leq 1000 $ **Objective** Compute $ \mathbb{E}[T] \mod 998244353 $, expressed as $ x \in [0, 998244352] $ such that $ x \cdot q \equiv p \pmod{998244353} $, where $ \mathbb{E}[T] = \frac{p}{q} $ in lowest terms.

API Response (JSON)

{
  "problem": {
    "name": "I. Ehab The Baby Learned Graphs",
    "description": {
      "content": "After learning to walk, Ehab the baby started learning graph theory. He never found the definition of the $x o r$ of 2 graphs, so he decided that the $x o r$ of 2 undirected graphs having the same num",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10288I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "After learning to walk, Ehab the baby started learning graph theory. He never found the definition of the $x o r$ of 2 graphs, so he decided that the $x o r$ of 2 undirected graphs having the same num...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $. Define the graph $ K_{n,m} $ as the complete bipartite graph with bipartition $ (U, V) $, where $ |U| = n $, $ |V| = m $, and every vertex in $ U $ is ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments