Graph Algorithms Jul 08, 2025

Problem A. Counting Rooms

Time Limit 1000 ms
Mem Limit 524288 kB

You are given a map of a building, and your task is to count the number of its rooms. The
size of the map is n × m squares, and each square is either floor or wall. You can walk left,
right, up, and down through the floor squares.

Input

The first input line has two integers n and m: the height and width of the map.

Then there are n lines of m characters describing the map. Each character is either .
(floor) or # (wall).

Output

Print one integer: the number of rooms.

Constraints

1 ≤ n, m ≤ 1000

Example

Input Output

5 8 3
########
#..#...#
####.#.#
#..#...#
########

Page 1 of 39
-
 Graph Algorithms Jul 08, 2025

Problem B. Labyrinth
Time Limit 1000 ms
Mem Limit 524288 kB

You are given a map of a labyrinth, and your task is to find a path from start to end. You
can walk left, right, up and down.

Input

The first input line has two integers n and m: the height and width of the map.

Then there are n lines of m characters describing the labyrinth. Each character is .
(floor), # (wall), A (start), or B (end). There is exactly one A and one B in the input.

Output

First print "YES", if there is a path, and "NO" otherwise.

If there is a path, print the length of the shortest such path and its description as a string
consisting of characters L (left), R (right), U (up), and D (down). You can print any
valid solution.

Constraints

1 ≤ n, m ≤ 1000

Example

Input Output

5 8 YES
######## 9
#.A#...# LDDRRRRRU
#.##.#B#
#......#
########

Page 2 of 39
-
 Graph Algorithms Jul 08, 2025

Problem C. Building Roads

Time Limit 1000 ms
Mem Limit 524288 kB

Byteland has n cities, and m roads between them. The goal is to construct new roads so
that there is a route between any two cities.

Your task is to find out the minimum number of roads required, and also determine which
roads should be built.

Input

The first input line has two integers n and m: the number of cities and roads. The cities
are numbered 1, 2, … , n.

After that, there are m lines describing the roads. Each line has two integers a and b: there
is a road between those cities.

A road always connects two different cities, and there is at most one road between any
two cities.

Output

First print an integer k : the number of required roads.

Then, print k lines that describe the new roads. You can print any valid solution.

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

4 2 1
1 2 2 3
3 4

Page 3 of 39
-
 Graph Algorithms Jul 08, 2025

Problem D. Message Route

Time Limit 1000 ms
Mem Limit 524288 kB

Syrjälä's network has n computers and m connections. Your task is to find out if Uolevi
can send a message to Maija, and if it is possible, what is the minimum number of
computers on such a route.

Input

The first input line has two integers n and m: the number of computers and connections.
The computers are numbered 1, 2, … , n. Uolevi's computer is 1 and Maija's computer is
n.

Then, there are m lines describing the connections. Each line has two integers a and b:
there is a connection between those computers.

Every connection is between two different computers, and there is at most one
connection between any two computers.

Output

If it is possible to send a message, first print k : the minimum number of computers on a

valid route. After this, print an example of such a route. You can print any valid solution.

If there are no routes, print "IMPOSSIBLE".

Constraints

2 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 4 of 39
-
 Graph Algorithms Jul 08, 2025

Problem E. Building Teams

Time Limit 1000 ms
Mem Limit 524288 kB

There are n pupils in Uolevi's class, and m friendships between them. Your task is to
divide the pupils into two teams in such a way that no two pupils in a team are friends.
You can freely choose the sizes of the teams.

Input

The first input line has two integers n and m: the number of pupils and friendships. The
pupils are numbered 1, 2, … , n.

Then, there are m lines describing the friendships. Each line has two integers a and b:
pupils a and b are friends.

Every friendship is between two different pupils. You can assume that there is at most one
friendship between any two pupils.

Output

Print an example of how to build the teams. For each pupil, print "1" or "2" depending on
to which team the pupil will be assigned. You can print any valid team.

If there are no solutions, print "IMPOSSIBLE".

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 5 of 39
-
 Graph Algorithms Jul 08, 2025

Problem F. Round Trip

Time Limit 1000 ms
Mem Limit 524288 kB

Byteland has n cities and m roads between them. Your task is to design a round trip that
begins in a city, goes through two or more other cities, and finally returns to the starting
city. Every intermediate city on the route has to be distinct.

Input

The first input line has two integers n and m: the number of cities and roads. The cities
are numbered 1, 2, … , n.

Then, there are m lines describing the roads. Each line has two integers a and b: there is a
road between those cities.

Every road is between two different cities, and there is at most one road between any two
cities.

Output

First print an integer k : the number of cities on the route. Then print k cities in the order
they will be visited. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 6 of 39
-
 Graph Algorithms Jul 08, 2025

Problem G. Monsters
Time Limit 1000 ms
Mem Limit 524288 kB

Imagine you are an adventurer named Alex trapped in an ancient labyrinth filled with
deadly monsters. The labyrinth is a grid of squares, where each square can either be an
open floor, a solid wall, your starting point, or occupied by a monster. Every time you
move one step in any direction, each monster also takes one step simultaneously. Your
mission is to find a way to escape to any boundary square of the labyrinth without ever
sharing a square with a monster. To do this, you need to determine if escaping is possible
and, if so, identify a path you can take that guarantees your safety no matter how the
monsters move. Keep in mind that the monsters can predict your movements, so your
plan must be foolproof under any circumstances.

To accomplish this, you need to determine if escaping is possible and, if so, identify a path
you can take that guarantees your safety no matter how the monsters move. Keep in mind
that the monsters can predict your movements, so your plan must be foolproof under any
circumstances.

Input

The first input line has two integers n and m: the height and width of the map.

After this there are n lines of m characters describing the map. Each character is .
(floor), # (wall), A (start), or M (monster). There is exactly one A in the input.

Output

First print "YES" if your goal is possible, and "NO" otherwise.

If your goal is possible, also print an example of a valid path (the length of the path and its
description using characters D , U , L , and R ). You can print any path, as long as its
length is at most n ⋅ m steps.

Constraints

1 ≤ n, m ≤ 1000

Example

Page 7 of 39
-
 Graph Algorithms Jul 08, 2025

Input Output

5 8 YES
######## 5
#M..A..# RRDDR
#.#.M#.#
#M#..#..
#.######

Page 8 of 39
-
 Graph Algorithms Jul 08, 2025

Problem H. Shortest Routes I

Time Limit 1000 ms
Mem Limit 524288 kB

There are n cities and m flight connections between them. Your task is to determine the
length of the shortest route from Syrjälä to every city.

Input

The first input line has two integers n and m: the number of cities and flight connections.
The cities are numbered 1, 2, … , n, and city 1 is Syrjälä.

After that, there are m lines describing the flight connections. Each line has three integers
a, b and c: a flight begins at city a, ends at city b, and its length is c. Each flight is a one-
way flight.

You can assume that it is possible to travel from Syrjälä to all other cities.

Output

Print n integers: the shortest route lengths from Syrjälä to cities 1, 2, … , n.

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
1 ≤ c ≤ 109

Example

Input Output

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

Page 9 of 39
-
 Graph Algorithms Jul 08, 2025

Problem I. Shortest Routes II

Time Limit 1000 ms
Mem Limit 524288 kB

There are n cities and m roads between them. Your task is to process q queries where you
have to determine the length of the shortest route between two given cities.

Input

The first input line has three integers n, m and q : the number of cities, roads, and queries.

Then, there are m lines describing the roads. Each line has three integers a, b and c: there
is a road between cities a and b whose length is c. All roads are two-way roads.

Finally, there are q lines describing the queries. Each line has two integers a and b:
determine the length of the shortest route between cities a and b.

Output

Print the length of the shortest route for each query. If there is no route, print −1 instead.

Constraints

1 ≤ n ≤ 500
1 ≤ m ≤ n2
1 ≤ q ≤ 105
1 ≤ a, b ≤ n
1 ≤ c ≤ 109

Example

Input Output

4 3 5 5
1 2 5 5
1 3 9 8
2 3 3 -1
1 2 3
2 1
1 3
1 4
3 2

Page 10 of 39
-
 Graph Algorithms Jul 08, 2025

Problem J. High Score

Time Limit 1000 ms
Mem Limit 524288 kB

You play a game consisting of n rooms and m tunnels. Your initial score is 0, and each
tunnel increases your score by x where x may be both positive or negative. You may go
through a tunnel several times.

Your task is to walk from room 1 to room n. What is the maximum score you can get?

Input

The first input line has two integers n and m: the number of rooms and tunnels. The
rooms are numbered 1, 2, … , n.

Then, there are m lines describing the tunnels. Each line has three integers a, b and x: the
tunnel starts at room a, ends at room b, and it increases your score by x. All tunnels are
one-way tunnels.

You can assume that it is possible to get from room 1 to room n.

Output

Print one integer: the maximum score you can get. However, if you can get an arbitrarily
large score, print −1.

Constraints

1 ≤ n ≤ 2500
1 ≤ m ≤ 5000
1 ≤ a, b ≤ n
−109 ≤ x ≤ 109

Example

Input Output

4 5 5
1 2 3
2 4 -1
1 3 -2
3 4 7
1 4 4

Page 11 of 39
-
 Graph Algorithms Jul 08, 2025

Problem K. Flight Discount

Time Limit 1000 ms
Mem Limit 524288 kB

Your task is to find a minimum-price flight route from Syrjälä to Metsälä. You have one
discount coupon, using which you can halve the price of any single flight during the route.
However, you can only use the coupon once.

When you use the discount coupon for a flight whose price is x, its price becomes ⌊x/2⌋
(it is rounded down to an integer).

Input

The first input line has two integers n and m: the number of cities and flight connections.
The cities are numbered 1, 2, … , n. City 1 is Syrjälä, and city n is Metsälä.

After this there are m lines describing the flights. Each line has three integers a, b, and c:
a flight begins at city a, ends at city b, and its price is c. Each flight is unidirectional.

You can assume that it is always possible to get from Syrjälä to Metsälä.

Output

Print one integer: the price of the cheapest route from Syrjälä to Metsälä.

Constraints

2 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
1 ≤ c ≤ 109

Example

Input Output

3 4 2
1 2 3
2 3 1
1 3 7
2 1 5

Page 12 of 39
-
 Graph Algorithms Jul 08, 2025

Problem L. Cycle Finding

Time Limit 1000 ms
Mem Limit 524288 kB

You are given a directed graph, and your task is to find out if it contains a negative cycle,
and also give an example of such a cycle.

Input

The first input line has two integers n and m: the number of nodes and edges. The nodes
are numbered 1, 2, … , n.

After this, the input has m lines describing the edges. Each line has three integers a, b,
and c: there is an edge from node a to node b whose length is c.

Output

If the graph contains a negative cycle, print first "YES", and then the nodes in the cycle in
their correct order. If there are several negative cycles, you can print any of them. If there
are no negative cycles, print "NO".

Constraints

1 ≤ n ≤ 2500
1 ≤ m ≤ 5000
1 ≤ a, b ≤ n
−109 ≤ c ≤ 109

Example

Input Output

4 5 YES
1 2 1 1 2 4 1
2 4 1
3 1 1
4 1 -3
4 3 -2

Page 13 of 39
-
 Graph Algorithms Jul 08, 2025

Problem M. Flight Routes

Time Limit 1000 ms
Mem Limit 524288 kB

Your task is to find the k shortest flight routes from Syrjälä to Metsälä. A route can visit
the same city several times.

Note that there can be several routes with the same price and each of them should be
considered (see the example).

Input

The first input line has three integers n, m, and k : the number of cities, the number of
flights, and the parameter k . The cities are numbered 1, 2, … , n. City 1 is Syrjälä, and city
n is Metsälä.

After this, the input has m lines describing the flights. Each line has three integers a, b,
and c: a flight begins at city a, ends at city b, and its price is c. All flights are one-way
flights.

You may assume that there are at least k distinct routes from Syrjälä to Metsälä.

Output

Print k integers: the prices of the k cheapest routes sorted according to their prices.

Constraints

2 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
1 ≤ c ≤ 109
1 ≤ k ≤ 10

Example

Input Output

4 6 3 4 4 7
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1

Page 14 of 39
-
 Graph Algorithms Jul 08, 2025

Explanation: The cheapest routes are 1 → 3 → 4 (price 4), 1 → 2 → 3 → 4 (price 4) and

1 → 2 → 4 (price 7).

Page 15 of 39
-
 Graph Algorithms Jul 08, 2025

Problem N. Round Trip II

Time Limit 1000 ms
Mem Limit 524288 kB

Byteland has n cities and m flight connections. Your task is to design a round trip that
begins in a city, goes through one or more other cities, and finally returns to the starting
city. Every intermediate city on the route has to be distinct.

Input

The first input line has two integers n and m: the number of cities and flights. The cities
are numbered 1, 2, … , n.

Then, there are m lines describing the flights. Each line has two integers a and b: there is
a flight connection from city a to city b. All connections are one-way flights from a city to
another city.

Output

First print an integer k : the number of cities on the route. Then print k cities in the order
they will be visited. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 16 of 39
-
 Graph Algorithms Jul 08, 2025

Problem O. Course Schedule

Time Limit 1000 ms
Mem Limit 524288 kB

You have to complete n courses. There are m requirements of the form "course a has to be
completed before course b". Your task is to find an order in which you can complete the
courses.

Input

The first input line has two integers n and m: the number of courses and requirements.
The courses are numbered 1, 2, … , n.

After this, there are m lines describing the requirements. Each line has two integers a and
b: course a has to be completed before course b.

Output

Print an order in which you can complete the courses. You can print any valid order that
includes all the courses.

If there are no solutions, print "IMPOSSIBLE".

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 17 of 39
-
 Graph Algorithms Jul 08, 2025

Problem P. Longest Flight Route

Time Limit 1000 ms
Mem Limit 524288 kB

Uolevi has won a contest, and the prize is a free flight trip that can consist of one or more
flights through cities. Of course, Uolevi wants to choose a trip that has as many cities as
possible.

Uolevi wants to fly from Syrjälä to Lehmälä so that he visits the maximum number of
cities. You are given the list of possible flights, and you know that there are no directed
cycles in the flight network.

Input

The first input line has two integers n and m: the number of cities and flights. The cities
are numbered 1, 2, … , n. City 1 is Syrjälä, and city n is Lehmälä.

After this, there are m lines describing the flights. Each line has two integers a and b:
there is a flight from city a to city b. Each flight is a one-way flight.

Output

First print the maximum number of cities on the route. After this, print the cities in the
order they will be visited. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

2 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 18 of 39
-
 Graph Algorithms Jul 08, 2025

Problem Q. Game Routes

Time Limit 1000 ms
Mem Limit 524288 kB

A game has n levels, connected by m teleporters, and your task is to get from level 1 to
level n. The game has been designed so that there are no directed cycles in the underlying
graph. In how many ways can you complete the game?

Input

The first input line has two integers n and m: the number of levels and teleporters. The
levels are numbered 1, 2, … , n.

After this, there are m lines describing the teleporters. Each line has two integers a and b:
there is a teleporter from level a to level b.

Output

Print one integer: the number of ways you can complete the game. Since the result may be
large, print it modulo 109 + 7.

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 19 of 39
-
 Graph Algorithms Jul 08, 2025

Problem R. Investigation
Time Limit 1000 ms
Mem Limit 524288 kB

You are going to travel from Syrjälä to Lehmälä by plane. You would like to find answers
to the following questions:

what is the minimum price of such a route?

how many minimum-price routes are there? (modulo 109 + 7)
what is the minimum number of flights in a minimum-price route?
what is the maximum number of flights in a minimum-price route?

Input

The first input line contains two integers n and m: the number of cities and the number of
flights. The cities are numbered 1, 2, … , n. City 1 is Syrjälä, and city n is Lehmälä.

After this, there are m lines describing the flights. Each line has three integers a, b, and c:
there is a flight from city a to city b with price c. All flights are one-way flights.

You may assume that there is a route from Syrjälä to Lehmälä.

Output

Print four integers according to the problem statement.

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
1 ≤ c ≤ 109

Example

Input Output

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

Page 20 of 39
-
 Graph Algorithms Jul 08, 2025

Problem S. Planets Queries I

Time Limit 1000 ms
Mem Limit 524288 kB

You are playing a game consisting of n planets. Each planet has a teleporter to another
planet (or the planet itself).

Your task is to process q queries of the form: when you begin on planet x and travel
through k teleporters, which planet will you reach?

Input

The first input line has two integers n and q : the number of planets and queries. The
planets are numbered 1, 2, … , n.

The second line has n integers t1 , t2 , … , tn : for each planet, the destination of the
​ ​ ​

teleporter. It is possible that ti ​

= i.

Finally, there are q lines describing the queries. Each line has two integers x and k : you
start on planet x and travel through k teleporters.

Output

Print the answer to each query.

Constraints

1 ≤ n, q ≤ 2 ⋅ 105
1 ≤ ti ≤ n
​

1≤x≤n
0 ≤ k ≤ 109

Example

Input Output

4 3 1
2 1 1 4 2
1 2 4
3 4
4 1

Page 21 of 39
-
 Graph Algorithms Jul 08, 2025

Problem T. Planets Queries II

Time Limit 1000 ms
Mem Limit 524288 kB

You are playing a game consisting of n planets. Each planet has a teleporter to another
planet (or the planet itself).

You have to process q queries of the form: You are now on planet a and want to reach
planet b. What is the minimum number of teleportations?

Input

The first input line contains two integers n and q : the number of planets and queries. The
planets are numbered 1, 2, … , n.

The second line contains n integers t1 , t2 , … , tn : for each planet, the destination of the
​ ​ ​

teleporter.

Finally, there are q lines describing the queries. Each line has two integers a and b: you are
now on planet a and want to reach planet b.

Output

For each query, print the minimum number of teleportations. If it is not possible to reach
the destination, print −1.

Constraints

1 ≤ n, q ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

5 3 1
2 3 2 3 2 2
1 2 -1
1 3
1 4

Page 22 of 39
-
 Graph Algorithms Jul 08, 2025

Problem U. Planets Cycles

Time Limit 1000 ms
Mem Limit 524288 kB

You are playing a game consisting of n planets. Each planet has a teleporter to another
planet (or the planet itself).

You start on a planet and then travel through teleporters until you reach a planet that you
have already visited before.

Your task is to calculate for each planet the number of teleportations there would be if you
started on that planet.

Input

The first input line has an integer n: the number of planets. The planets are numbered
1, 2, … , n.

The second line has n integers t1 , t2 , … , tn : for each planet, the destination of the
​ ​ ​

teleporter. It is possible that ti ​

= i.

Output

Print n integers according to the problem statement.

Constraints

1 ≤ n ≤ 2 ⋅ 105
1 ≤ ti ≤ n
​

Example

Input Output

5 3 3 1 3 4
2 4 3 1 4

Page 23 of 39
-
 Graph Algorithms Jul 08, 2025

Problem V. Road Reparation

Time Limit 1000 ms
Mem Limit 131072 kB

There are n cities and m roads between them. Unfortunately, the condition of the roads is
so poor that they cannot be used. Your task is to repair some of the roads so that there will
be a decent route between any two cities.

For each road, you know its reparation cost, and you should find a solution where the
total cost is as small as possible.

Input

The first input line has two integers n and m: the number of cities and roads. The cities
are numbered 1, 2, … , n.

Then, there are m lines describing the roads. Each line has three integers a, b and c: there
is a road between cities a and b, and its reparation cost is c. All roads are two-way roads.

Every road is between two different cities, and there is at most one road between two
cities.

Output

Print one integer: the minimum total reparation cost. However, if there are no solutions,
print "IMPOSSIBLE".

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
1 ≤ c ≤ 109

Example

Page 24 of 39
-
 Graph Algorithms Jul 08, 2025

Input Output

5 6 14
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4

Page 25 of 39
-
 Graph Algorithms Jul 08, 2025

Problem W. Road Construction

Time Limit 1000 ms
Mem Limit 524288 kB

There are n cities and initially no roads between them. However, every day a new road will
be constructed, and there will be a total of m roads.

A component is a group of cities where there is a route between any two cities using the
roads. After each day, your task is to find the number of components and the size of the
largest component.

Input

The first input line has two integers n and m: the number of cities and roads. The cities
are numbered 1, 2, … , n.

Then, there are m lines describing the new roads. Each line has two integers a and b: a
new road is constructed between cities a and b.

You may assume that every road will be constructed between two different cities.

Output

Print m lines: the required information after each day.

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 26 of 39
-
 Graph Algorithms Jul 08, 2025

Problem X. Flight Routes Check

Time Limit 1000 ms
Mem Limit 524288 kB

There are n cities and m flight connections. Your task is to check if you can travel from
any city to any other city using the available flights.

Input

The first input line has two integers n and m: the number of cities and flights. The cities
are numbered 1, 2, … , n.

After this, there are m lines describing the flights. Each line has two integers a and b:
there is a flight from city a to city b. All flights are one-way flights.

Output

Print "YES" if all routes are possible, and "NO" otherwise. In the latter case also print two
cities a and b such that you cannot travel from city a to city b. If there are several possible
solutions, you can print any of them.

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

4 5 NO
1 2 4 2
2 3
3 1
1 4
3 4

Page 27 of 39
-
 Graph Algorithms Jul 08, 2025

Problem Y. Planets and Kingdoms

Time Limit 1000 ms
Mem Limit 524288 kB

A game has n planets, connected by m teleporters. Two planets a and b belong to the same
kingdom exactly when there is a route both from a to b and from b to a. Your task is to
determine for each planet its kingdom.

Input

The first input line has two integers n and m: the number of planets and teleporters. The
planets are numbered 1, 2, … , n.

After this, there are m lines describing the teleporters. Each line has two integers a and b:
you can travel from planet a to planet b through a teleporter.

Output

First print an integer k : the number of kingdoms. After this, print for each planet a
kingdom label between 1 and k . You can print any valid solution.

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 28 of 39
-
 Graph Algorithms Jul 08, 2025

Problem Z. Giant Pizza

Time Limit 1000 ms
Mem Limit 524288 kB

Uolevi's family is going to order a large pizza and eat it together. A total of n family
members will join the order, and there are m possible toppings. The pizza may have any
number of toppings.

Each family member gives two wishes concerning the toppings of the pizza. The wishes
are of the form "topping x is good/bad". Your task is to choose the toppings so that at
least one wish from everybody becomes true (a good topping is included in the pizza or a
bad topping is not included).

Input

The first input line has two integers n and m: the number of family members and
toppings. The toppings are numbered 1, 2, … , m.

After this, there are n lines describing the wishes. Each line has two wishes of the form "+
x" (topping x is good) or "- x" (topping x is bad).

Output

Print a line with m symbols: for each topping "+" if it is included and "-" if it is not
included. You can print any valid solution.

If there are no valid solutions, print "IMPOSSIBLE".

Constraints

1 ≤ n, m ≤ 105
1≤x≤m

Example

Input Output

3 5 - + + + -
+ 1 + 2
- 1 + 3
+ 4 - 2

Page 29 of 39
-
 Graph Algorithms Jul 08, 2025

Problem AA. Coin Collector

Time Limit 1000 ms
Mem Limit 524288 kB

A game has n rooms and m tunnels between them. Each room has a certain number of
coins. What is the maximum number of coins you can collect while moving through the
tunnels when you can freely choose your starting and ending room?

Input

The first input line has two integers n and m: the number of rooms and tunnels. The
rooms are numbered 1, 2, … , n.

Then, there are n integers k1 , k2 , … , kn : the number of coins in each room.

​ ​ ​

Finally, there are m lines describing the tunnels. Each line has two integers a and b: there
is a tunnel from room a to room b. Each tunnel is a one-way tunnel.

Output

Print one integer: the maximum number of coins you can collect.

Constraints

1 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ ki ≤ 109
​

1 ≤ a, b ≤ n

Example

Input Output

4 4 16
4 5 2 7
1 2
2 1
1 3
2 4

Page 30 of 39
-
 Graph Algorithms Jul 08, 2025

Problem AB. Mail Delivery

Time Limit 1000 ms
Mem Limit 524288 kB

Your task is to deliver mail to the inhabitants of a city. For this reason, you want to find a
route whose starting and ending point are the post office, and that goes through every
street exactly once.

Input

The first input line has two integers n and m: the number of crossings and streets. The
crossings are numbered 1, 2, … , n, and the post office is located at crossing 1.

After that, there are m lines describing the streets. Each line has two integers a and b:
there is a street between crossings a and b. All streets are two-way streets.

Every street is between two different crossings, and there is at most one street between
two crossings.

Output

Print all the crossings on the route in the order you will visit them. You can print any valid
solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

2 ≤ n ≤ 105
1 ≤ m ≤ 2.105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 31 of 39
-
 Graph Algorithms Jul 08, 2025

Problem AC. De Bruijn Sequence

Time Limit 1000 ms
Mem Limit 524288 kB

Your task is to construct a minimum-length bit string that contains all possible
substrings of length n. For example, when n = 2, the string 00110 is a valid solution,
because its substrings of length 2 are 00, 01, 10 and 11.

Input

The only input line has an integer n.

Output

Print a minimum-length bit string that contains all substrings of length n. You can print
any valid solution.

Constraints

1 ≤ n ≤ 15

Example

Input Output

2 00110

Page 32 of 39
-
 Graph Algorithms Jul 08, 2025

Problem AD. Teleporters Path

Time Limit 1000 ms
Mem Limit 524288 kB

A game has n levels and m teleportes between them. You win the game if you move from
level 1 to level n using every teleporter exactly once.

Can you win the game, and what is a possible way to do it?

Input

The first input line has two integers n and m: the number of levels and teleporters. The
levels are numbered 1, 2, … , n.

Then, there are m lines describing the teleporters. Each line has two integers a and b:
there is a teleporter from level a to level b.

You can assume that each pair (a, b) in the input is distinct.

Output

Print m + 1 integers: the sequence in which you visit the levels during the game. You can
print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

2 ≤ n ≤ 105
1 ≤ m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n

Example

Input Output

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

Page 33 of 39
-
 Graph Algorithms Jul 08, 2025

Problem AE. Hamiltonian Flights

Time Limit 1000 ms
Mem Limit 524288 kB

There are n cities and m flight connections between them. You want to travel from Syrjälä
to Lehmälä so that you visit each city exactly once. How many possible routes are there?

Input

The first input line has two integers n and m: the number of cities and flights. The cities
are numbered 1, 2, … , n. City 1 is Syrjälä, and city n is Lehmälä.

Then, there are m lines describing the flights. Each line has two integers a and b: there is
a flight from city a to city b. All flights are one-way flights.

Output

Print one integer: the number of routes modulo 109 + 7.

Constraints

2 ≤ n ≤ 20
1 ≤ m ≤ n2
1 ≤ a, b ≤ n

Example

Input Output

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

Page 34 of 39
-
 Graph Algorithms Jul 08, 2025

Problem AF. Knight's Tour

Time Limit 1000 ms
Mem Limit 524288 kB

Given a starting position of a knight on an 8 × 8 chessboard, your task is to find a

sequence of moves such that it visits every square exactly once.

On each move, the knight may either move two steps horizontally and one step vertically,
or one step horizontally and two steps vertically.

Input

The only line has two integers x and y : the knight's starting position.

Output

Print a grid that shows how the knight moves (according to the example). You can print
any valid solution.

Constraints

1 ≤ x, y ≤ 8

Example

Input Output

2 1 8 1 10 13 6 3 20 17
11 14 7 2 19 16 23 4
26 9 12 15 24 5 18 21
49 58 25 28 51 22 33 30
40 27 50 59 32 29 52 35
57 48 41 44 37 34 31 62
42 39 46 55 60 63 36 53
47 56 43 38 45 54 61 64

Page 35 of 39
-
 Graph Algorithms Jul 08, 2025

Problem AG. Download Speed

Time Limit 1000 ms
Mem Limit 524288 kB

Consider a network consisting of n computers and m connections. Each connection

specifies how fast a computer can send data to another computer.

Kotivalo wants to download some data from a server. What is the maximum speed he can
do this, using the connections in the network?

Input

The first input line has two integers n and m: the number of computers and connections.
The computers are numbered 1, 2, … , n. Computer 1 is the server and computer n is
Kotivalo's computer.

After this, there are m lines describing the connections. Each line has three integers a, b
and c: computer a can send data to computer b at speed c.

Output

Print one integer: the maximum speed Kotivalo can download data.

Constraints

1 ≤ n ≤ 500
1 ≤ m ≤ 1000
1 ≤ a, b ≤ n
1 ≤ c ≤ 109

Example

Input Output

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

Page 36 of 39
-
 Graph Algorithms Jul 08, 2025

Problem AH. Police Chase

Time Limit 1000 ms
Mem Limit 524288 kB

Kaaleppi has just robbed a bank and is now heading to the harbor. However, the police
wants to stop him by closing some streets of the city.

What is the minimum number of streets that should be closed so that there is no route
between the bank and the harbor?

Input

The first input line has two integers n and m: the number of crossings and streets. The
crossings are numbered 1, 2, … , n. The bank is located at crossing 1, and the harbor is
located at crossing n.

After this, there are m lines that describing the streets. Each line has two integers a and b:
there is a street between crossings a and b. All streets are two-way streets, and there is at
most one street between two crossings.

Output

First print an integer k : the minimum number of streets that should be closed. After this,
print k lines describing the streets. You can print any valid solution.

Constraints

2 ≤ n ≤ 500
1 ≤ m ≤ 1000
1 ≤ a, b ≤ n

Example

Input Output

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

Page 37 of 39
-
 Graph Algorithms Jul 08, 2025

Problem AI. School Dance

Time Limit 1000 ms
Mem Limit 524288 kB

There are n boys and m girls in a school. Next week a school dance will be organized. A
dance pair consists of a boy and a girl, and there are k potential pairs.

Your task is to find out the maximum number of dance pairs and show how this number
can be achieved.

Input

The first input line has three integers n, m and k : the number of boys, girls, and potential
pairs. The boys are numbered 1, 2, … , n, and the girls are numbered 1, 2, … , m.

After this, there are k lines describing the potential pairs. Each line has two integers a and
b: boy a and girl b are willing to dance together.

Output

First print one integer r : the maximum number of dance pairs. After this, print r lines
describing the pairs. You can print any valid solution.

Constraints

1 ≤ n, m ≤ 500
1 ≤ k ≤ 1000
1≤a≤n
1≤b≤m

Example

Input Output

3 2 4 2
1 1 1 2
1 2 3 1
2 1
3 1

Page 38 of 39
-
 Graph Algorithms Jul 08, 2025

Problem AJ. Distinct Routes

Time Limit 1000 ms
Mem Limit 524288 kB

A game consists of n rooms and m teleporters. At the beginning of each day, you start in
room 1 and you have to reach room n.

You can use each teleporter at most once during the game. How many days can you play if
you choose your routes optimally?

Input

The first input line has two integers n and m: the number of rooms and teleporters. The
rooms are numbered 1, 2, … , n.

After this, there are m lines describing the teleporters. Each line has two integers a and b:
there is a teleporter from room a to room b.

There are no two teleporters whose starting and ending room are the same.

Output

First print an integer k : the maximum number of days you can play the game. Then, print
k route descriptions according to the example. You can print any valid solution.

Constraints

2 ≤ n ≤ 500
1 ≤ m ≤ 1000
1 ≤ a, b ≤ n

Example

Input Output

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

Page 39 of 39
-