[Solution] Formalism for Formalism Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Formalism for Formalism Codeforces Solution | Codeforces Problem Solution 2022

F. Formalism for Formalism

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Yura is a mathematician, and his cognition of the world is so absolute as if he have been solving formal problems a hundred of trillions of billions of years. This problem is just that!

Consider all non-negative integers from the interval [0,10𝑛)$[0,{10}^n)$. For convenience we complement all numbers with leading zeros in such way that each number from the given interval consists of exactly 𝑛$n$ decimal digits.

Solution Click Below:-  CLICK HERE

You are given a set of pairs (𝑢𝑖,𝑣𝑖)$(u_i,v_i)$, where 𝑢𝑖$u_i$ and 𝑣𝑖$v_i$ are distinct decimal digits from 0$0$ to 9$9$.

Consider a number 𝑥$x$ consisting of 𝑛$n$ digits. We will enumerate all digits from left to right and denote them as 𝑑1,𝑑2,…,𝑑𝑛$d_1,d_2,\dots ,d_n$. In one operation you can swap digits 𝑑𝑖$d_i$ and 𝑑𝑖+1$d_{i+1}$ if and only if there is a pair (𝑢𝑗,𝑣𝑗)$(u_j,v_j)$ in the set such that at least one of the following conditions is satisfied:

1. 𝑑𝑖=𝑢𝑗$d_i=u_j$ and 𝑑𝑖+1=𝑣𝑗$d_{i+1}=v_j$,
2. 𝑑𝑖=𝑣𝑗$d_i=v_j$ and 𝑑𝑖+1=𝑢𝑗$d_{i+1}=u_j$.

AvtoBus Codeforces Solution

Stone Age Problem Codeforces Solution

Rooks Defenders Codeforces Solution

Toss a Coin to Your Graph... Codeforces Solution

Typical Party in Dorm Codeforces Solution

Formalism for Formalism Codeforces Solution 

We will call the numbers 𝑥$x$ and 𝑦$y$, consisting of 𝑛$n$ digits, equivalent if the number 𝑥$x$ can be transformed into the number 𝑦$y$ using some number of operations described above. In particular, every number is considered equivalent to itself.

You are given an integer 𝑛$n$ and a set of 𝑚$m$ pairs of digits (𝑢𝑖,𝑣𝑖)$(u_i,v_i)$. You have to find the maximum integer 𝑘$k$ such that there exists a set of integers 𝑥1,𝑥2,…,𝑥𝑘$x_1,x_2,\dots ,x_k$ (0≤𝑥𝑖<10𝑛$0\le x_i<{10}^n$) such that for each 1≤𝑖<𝑗≤𝑘$1\le i<j\le k$ the number 𝑥𝑖$x_i$ is not equivalent to the number 𝑥𝑗$x_j$.

Input

The first line contains an integer 𝑛$n$ (1≤𝑛≤50000$1\le n\le 50000$) — the number of digits in considered numbers.

The second line contains an integer 𝑚$m$ (0≤𝑚≤45$0\le m\le 45$) — the number of pairs of digits in the set.

Each of the following 𝑚$m$ lines contains two digits 𝑢𝑖$u_i$ and 𝑣𝑖$v_i$, separated with a space (0≤𝑢𝑖<𝑣𝑖≤9$0\le u_i<v_i\le 9$).

It's guaranteed that all described pairs are pairwise distinct.

Output

Print one integer — the maximum value 𝑘$k$ such that there exists a set of integers 𝑥1,𝑥2,…,𝑥𝑘$x_1,x_2,\dots ,x_k$ (0≤𝑥𝑖<10𝑛$0\le x_i<{10}^n$) such that for each 1≤𝑖<𝑗≤𝑘$1\le i<j\le k$ the number 𝑥𝑖$x_i$ is not equivalent to the number 𝑥𝑗$x_j$.

As the answer can be big enough, print the number 𝑘$k$ modulo 998244353$998244353$.

Join Now for Solution:-