Plus
Pin


Problem description Progress
ID 33469. *Stalker
Темы: 0-1 BFS    Dec   

In the city of N, under unclear circumstances, the territory of one of the factories turned into an anomalous zone. All entrances to the territory were blocked, and it itself was called the industrial zone. There are N buildings in the industrial zone, some of them are connected by roads. Any road can be traveled in both directions.
The novice stalker was given the task to get to the warehouse in the industrial zone. He found several maps of the territory of the industrial zone in the electronic archive. Since the maps were compiled by different people, each of them contains information only about some roads of the industrial zone. The same road can appear on several maps.
On the way, the stalker can download one card from the archive to the mobile phone. When you download a new map, the previous one is not stored in the phone's memory. The stalker can only move along the roads marked on the currently loaded map. Each map download costs 1 ruble. To minimize costs, the stalker needs to choose such a route in order to download maps as few times as possible. Stalker can download the same map several times, and you will have to pay for each download. Initially, there is no card in the mobile phone's memory.

It is required to write a program that calculates the minimum amount of expenses necessary for a stalker to get from the entrance to the industrial zone to the warehouse.

Input: 
- the first line of the input contains two natural numbers N and K (\(2 <= N <= 2000\ ); \(1 <= K <= 2000\)) — the number of industrial zone buildings and the number of maps, respectively. The entrance to the industrial zone is located in the building with the number 1, and the warehouse — in building number N.
- in the following lines there is information about the available cards. The first line of the description of the ith card contains the number ri — number of roads marked on the i-th map;
- then come ri strings containing two natural numbers a and b (\(1 <= a\), \(b <= N\); \(a ? b\)), meaning that there is a road on the i-th map connecting buildings a and b. The total number of roads marked on all maps does not exceed 300,000 (\(r_1 + r_2 + … + r_K <= 300,000\)).

Output: print a single number — the minimum amount of the stalker's expenses. If it is impossible to get to the warehouse, print the number –1.

 

 

Examples
# Input Output
1 12 4
4
16
24
79
10 12
3
14
7 11
36
3
25
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12
3

ID 38604. simple dec
Темы: Dec   

Implement the "dec" data structure.  Write a program containing a description of the deck and simulating the operation of the deck, implementing all the methods indicated here. The program reads a sequence of commands and, depending on the command, performs one or another operation. After executing each command, the program should print one line. Possible commands for the program:

push_front
Add (put) a new element to the beginning of the deck. The program should print ok.

push_back
Add (put) a new element to the end of the deck. The program should print ok.

pop_front
Extract the first element from the deque. The program should output its value.

pop_back
Extract the last element from the deque. The program should output its value.

front
Get the value of the first element (without removing it). The program should output its value.

back
Get the value of the last element (without removing it). The program should output its value.

size
Display the number of elements in the deck.

clear
Clear deque (remove all elements from it) and output ok.

exit
The program should print bye and exit.
It is guaranteed that the number of elements in the deck does not exceed 100 at any time. All operations pop_front, pop_back, front, back are always valid.

Input
Deck control commands are entered, one per line.

Imprint
It is required to display the log of the deck, one message per line.

Examples
# Input Output
1 push_back 1
back
exit
ok
1
bye
2 size
push_back 1

push_back 2

push_front 3

exit
0
ok
1
ok
2
ok
3
bye

ID 38605. Dec with error protection
Темы: Dec   

Implement the "dec" data structure.  Write a program containing a description of the deck and simulating the operation of the deck, implementing all the methods indicated here. The program reads a sequence of commands and, depending on the command, performs one or another operation. After executing each command, the program should print one line. Possible commands for the program:

push_front
Add (put) a new element to the beginning of the deck. The program should print ok.

push_back
Add (put) a new element to the end of the deck. The program should print ok.

pop_front
Extract the first element from the deque. The program should output its value.

pop_back
Extract the last element from the deque. The program should output its value.

front
Get the value of the first element (without removing it). The program should output its value.

back
Get the value of the last element (without removing it). The program should output its value.

size
Display the number of elements in the deck.

clear
Clear deque (remove all elements from it) and output ok.

exit
The program should print bye and exit.
It is guaranteed that the number of elements in the deck does not exceed 100 at any time. Before executing the operations pop_front, pop_back, front, back, the program must check whether the deck contains at least one element. If the input contains operations pop_front, pop_back, front, back, and at the same time the deque is empty, then the program should output the string error instead of a numeric value.

Input
Deck control commands are entered, one per line.

Imprint
It is required to display the log of the deck, one message per line

Examples
# Input Output
1 push_back 1
back
exit
ok
1
bye
2 size
push_back 1

push_back 2

push_front 3

exit
0
ok
1
ok
2
ok
3
bye