Problem Statement

There are N competitive programmers numbered person 1, person 2, \ldots, and person N.
There is a relation called superiority between the programmers. For all pairs of distinct programmers (person X, person Y), exactly one of the following two relations holds: "person X is stronger than person Y" or "person Y is stronger than person X."
The superiority is transitive. In other words, for all triplets of distinct programmers (person X, person Y, person Z), it holds that:

• if person X is stronger than person Y and person Y is stronger than person Z, then person X is stronger than person Z.

A person X is said to be the strongest programmer if person X is stronger than person Y for all people Y other than person X. (Under the constraints above, we can prove that there is always exactly one such person.)

You have M pieces of information on their superiority. The i-th of them is that "person A_i is stronger than person B_i."
Can you determine the strongest programmer among the N based on the information?
If you can, print the person's number. Otherwise, that is, if there are multiple possible strongest programmers, print -1.

Constraints

• 2 \leq N \leq 50
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• If i \neq j, then (A_i, B_i) \neq (A_j, B_j).
• There is at least one way to determine superiorities for all pairs of distinct programmers, that is consistent with the given information.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1

You have two pieces of information: "person 1 is stronger than person 2" and "person 2 is stronger than person 3."
By the transitivity, you can also infer that "person 1 is stronger than person 3," so person 1 is the strongest programmer.

Sample Input 2

3 2
1 3
2 3

Sample Output 2

-1

Both person 1 and person 2 may be the strongest programmer. Since you cannot uniquely determine which is the strongest, you should print -1.

Sample Input 3

6 6
1 6
6 5
6 2
2 3
4 3
4 2

Sample Output 3

-1

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N, each consisting of lowercase English letters. The lengths of these strings are all distinct.

Sort these strings in ascending order of length, and then concatenate them in that order to form a single string.

Constraints

• 2 \leq N \leq 50
• N is an integer.
• Each S_i is a string consisting of lowercase English letters with length between 1 and 50, inclusive.
• If i \neq j, the length of S_i is different from the length of S_j.

Sample Input 1

3
tc
oder
a

Sample Output 1

atcoder

When we sort (tc, oder, a) in ascending order of length, we get (a, tc, oder). Concatenating them in this order yields the string atcoder.

Sample Input 2

4
cat
enate
on
c

Sample Output 2

concatenate

Problem Statement

There are zero or more sensors placed on a grid of H rows and W columns. Let (i, j) denote the square in the i-th row from the top and the j-th column from the left.
Whether each square contains a sensor is given by the strings S_1, S_2, \ldots, S_H, each of length W. (i, j) contains a sensor if and only if the j-th character of S_i is #.
These sensors interact with other sensors in the squares horizontally, vertically, or diagonally adjacent to them and operate as one sensor. Here, a cell (x, y) and a cell (x', y') are said to be horizontally, vertically, or diagonally adjacent if and only if \max(|x-x'|,|y-y'|) = 1.
Note that if sensor A interacts with sensor B and sensor A interacts with sensor C, then sensor B and sensor C also interact.

Considering the interacting sensors as one sensor, find the number of sensors on this grid.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• S_i is a string of length W where each character is # or ..

Sample Input 1

5 6
.##...
...#..
....##
#.#...
..#...

Sample Output 1

3

When considering the interacting sensors as one sensor, the following three sensors exist:

• The interacting sensors at (1,2),(1,3),(2,4),(3,5),(3,6)
• The sensor at (4,1)
• The interacting sensors at (4,3),(5,3)

Sample Input 2

3 3
#.#
.#.
#.#

Sample Output 2

1

Sample Input 3

4 2
..
..
..
..

Sample Output 3

0

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

7

Problem Statement

This problem is a sub-problem of Problem F (Operate K), with K=1.
You can solve this problem by submitting a correct solution for Problem F to this problem.

Determine whether it is possible to perform the following operation on string S between 0 and K times, inclusive, to make it identical to string T.

• Choose one of the following three operations and execute it.
  • Insert any one character at any position in S (possibly the beginning or end).
  • Delete one character from S.
  • Choose one character in S and replace it with another character.

Constraints

• Each of S and T is a string of length between 1 and 500000, inclusive, consisting of lowercase English letters.
• \color{red}{K=1}

Sample Input 1

1
abc
agc

Sample Output 1

Yes

Replacing the second character b of abc with g converts abc to agc in one operation.

Sample Input 2

1
abc
awtf

Sample Output 2

No

abc cannot be converted to awtf in one operation.

Sample Input 3

1
abc
ac

Sample Output 3

Yes

Deleting the second character b of abc converts abc to ac in one operation.

Sample Input 4

1
back
black

Sample Output 4

Yes

Inserting l between the first and second characters of back converts back to black in one operation.

Sample Input 5

1
same
same

Sample Output 5

Yes

It is also possible that S = T from the beginning.

Sample Input 6

1
leap
read

Sample Output 6

No

Problem Statement

N cards, numbered 1 through N, are arranged in a line. For each i\ (1\leq i < N), card i and card (i+1) are adjacent to each other. Card i has A_i written on its front, and B_i written on its back. Initially, all cards are face up.

Consider flipping zero or more cards chosen from the N cards. Among the 2^N ways to choose the cards to flip, find the number, modulo 998244353, of such ways that:

• when the chosen cards are flipped, for every pair of adjacent cards, the integers written on their face-up sides are different.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq A_i,B_i \leq 10^9
• All values in the input are integers.

Sample Input 1

3
1 2
4 2
3 4

Sample Output 1

4

Let S be the set of card numbers to flip.

For example, when S=\{2,3\} is chosen, the integers written on their visible sides are 1,2, and 4, from card 1 to card 3, so it satisfies the condition.

On the other hand, when S=\{3\} is chosen, the integers written on their visible sides are 1,4, and 4, from card 1 to card 3, where the integers on card 2 and card 3 are the same, violating the condition.

Four S satisfy the conditions: \{\},\{1\},\{2\}, and \{2,3\}.

Sample Input 2

4
1 5
2 6
3 7
4 8

Sample Output 2

16

Sample Input 3

8
877914575 602436426
861648772 623690081
476190629 262703497
971407775 628894325
822804784 450968417
161735902 822804784
161735902 822804784
822804784 161735902

Sample Output 3

48