vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are n cities in Berland. The city numbered 1 is the capital. Some pairs of cities are connected by a one-way road of length 1.

Before the trip, Polycarp for each city found out the value of d_i — the shortest distance from the capital (the 1-st city) to the i-th city.

Polycarp begins his journey in the city with number s and, being in the i-th city, chooses one of the following actions: 

  1. Travel from the i-th city to the j-th city if there is a road from the i-th city to the j-th and d_i < d_j; 
  2. Travel from the i-th city to the j-th city if there is a road from the i-th city to the j-th and d_i ≥ d_j; 
  3. Stop traveling. 



Since the government of Berland does not want all people to come to the capital, so Polycarp no more than once can take the second action from the list. in other words, he can perform the second action 0 or 1 time during his journey. Polycarp, on the other hand, wants to be as close to the capital as possible.

<image>

For example, if n = 6 and the cities are connected, as in the picture above, then Polycarp could have made the following travels (not all possible options): 

  * 2 → 5 → 1 → 2 → 5; 
  * 3 → 6 → 2; 
  * 1 → 3 → 6 → 2 → 5. 



Polycarp wants for each starting city i to find out how close he can get to the capital. More formally: he wants to find the minimal value of d_j that Polycarp can get from the city i to the city j according to the rules described above.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

Each test case is preceded by an empty line.

The first line of each test case contains two integers n (2 ≤ n ≤ 2 ⋅ 10^5) and m (1 ≤ m ≤ 2 ⋅ 10^5) — number of cities and roads, respectively.

This is followed by m lines describing the roads. Each road is characterized by two integers u and v (1 ≤ u, v ≤ n, u ≠ v) — the numbers of cities connected by a one-way road.

It is guaranteed that the sums of n and m over all test cases do not exceed 2 ⋅ 10^5.

It is guaranteed that for each pair of different cities (u, v) there is at most one road from u to v (but a pair of roads from u to v and from v to u — is valid).

It is guaranteed that there is a path from the capital to all cities.

Output

For each test case, on a separate line output n numbers, the i-th of which is equal to the minimum possible distance from the capital to the city where Polycarp ended his journey.

Example

Input


3

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

2 2
1 2
2 1

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


Output


0 0 1 2 0 1 
0 0 
0 0 2 1 1 0 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

Chef will have N guests in his house today. He wants to serve at least one dish to each of the N guests. Chef can make two types of dishes. He needs one fruit and one vegetable to make the first type of dish and one vegetable and one fish to make the second type of dish. Now Chef has A fruits, B vegetables, and C fishes in his house. Can he prepare at least N dishes in total?

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains of a single line of input, four integers N, A, B, C.

------ Output Format ------ 

For each test case, print "YES" if Chef can prepare at least N dishes, otherwise print "NO". Print the output without quotes.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N, A, B, C ≤ 100$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
4
2 1 2 1
3 2 2 2
4 2 6 3
3 1 3 1

----- Sample Output 1 ------ 
YES
NO
YES
NO
----- explanation 1 ------ 
Test case $1$: Chef prepares one dish of the first type using one fruit and one vegetable and another dish of the second type using one vegetable and one fish.

Test case $2$: Chef prepares two dishes of the first type using two fruit and two vegetable. Now all the vegetables are exhausted, hence he can't prepare any other dishes.

Test case $3$: Chef can prepare a total of $5$ dishes, two dishes of the first type and three dishes of the second type.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sorted array arr containing n elements with possibly duplicate elements, the task is to find indexes of first and last occurrences of an element x in the given array.
Example 1:
Input:
n=9, x=5
arr[] = { 1, 3, 5, 5, 5, 5, 67, 123, 125 }
Output:  2 5
Explanation: First occurrence of 5 is at index 2 and last
             occurrence of 5 is at index 5. 
 
Example 2:
Input:
n=9, x=7
arr[] = { 1, 3, 5, 5, 5, 5, 7, 123, 125 }
Output:  6 6 
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function find() that takes array arr, integer n and integer x as parameters and returns the required answer.
Note: If the number x is not found in the array just return both index as -1.
 
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{7}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Tree Queries

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a tree consisting of *n* vertices (numbered from 1 to *n*). Initially all vertices are white. You have to process *q* queries of two different types:
 1.  1 *x* — change the color of vertex *x* to black. It is guaranteed that the first query will be of this type. 1.  2 *x* — for the vertex *x*, find the minimum index *y* such that the vertex with index *y* belongs to the simple path from *x* to some black vertex (a simple path never visits any vertex more than once). 
For each query of type 2 print the answer to it.

Note that the queries are given in modified way.

Input Specification:
The first line contains two numbers *n* and *q* (3<=≤<=*n*,<=*q*<=≤<=106).

Then *n*<=-<=1 lines follow, each line containing two numbers *x**i* and *y**i* (1<=≤<=*x**i*<=&lt;<=*y**i*<=≤<=*n*) and representing the edge between vertices *x**i* and *y**i*.

It is guaranteed that these edges form a tree.

Then *q* lines follow. Each line contains two integers *t**i* and *z**i*, where *t**i* is the type of *i*th query, and *z**i* can be used to restore *x**i* for this query in this way: you have to keep track of the answer to the last query of type 2 (let's call this answer *last*, and initially *last*<==<=0); then *x**i*<==<=(*z**i*<=+<=*last*)<=*mod*<=*n*<=+<=1.

It is guaranteed that the first query is of type 1, and there is at least one query of type 2.

Output Specification:
For each query of type 2 output the answer to it.

Demo Input:
['4 6\n1 2\n2 3\n3 4\n1 2\n1 2\n2 2\n1 3\n2 2\n2 2\n']

Demo Output:
['3\n2\n1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera runs a 24/7 fast food cafe. He magically learned that next day n people will visit his cafe. For each person we know the arrival time: the i-th person comes exactly at h_{i} hours m_{i} minutes. The cafe spends less than a minute to serve each client, but if a client comes in and sees that there is no free cash, than he doesn't want to wait and leaves the cafe immediately. 

Valera is very greedy, so he wants to serve all n customers next day (and get more profit). However, for that he needs to ensure that at each moment of time the number of working cashes is no less than the number of clients in the cafe. 

Help Valera count the minimum number of cashes to work at his cafe next day, so that they can serve all visitors.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5), that is the number of cafe visitors.

Each of the following n lines has two space-separated integers h_{i} and m_{i} (0 ≤ h_{i} ≤ 23; 0 ≤ m_{i} ≤ 59), representing the time when the i-th person comes into the cafe. 

Note that the time is given in the chronological order. All time is given within one 24-hour period.


-----Output-----

Print a single integer — the minimum number of cashes, needed to serve all clients next day.


-----Examples-----
Input
4
8 0
8 10
8 10
8 45

Output
2

Input
3
0 12
10 11
22 22

Output
1



-----Note-----

In the first sample it is not enough one cash to serve all clients, because two visitors will come into cafe in 8:10. Therefore, if there will be one cash in cafe, then one customer will be served by it, and another one will not wait and will go away.

In the second sample all visitors will come in different times, so it will be enough one cash.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Function Descriptions=====
.symmetric_difference()

The .symmetric_difference() operator returns a set with all the elements that are in the set and the iterable but not both.
Sometimes, a ^ operator is used in place of the .symmetric_difference() tool, but it only operates on the set of elements in set.
The set is immutable to the .symmetric_difference() operation (or ^ operation).

>>> s = set("Hacker")
>>> print s.symmetric_difference("Rank")
set(['c', 'e', 'H', 'n', 'R', 'r'])

>>> print s.symmetric_difference(set(['R', 'a', 'n', 'k']))
set(['c', 'e', 'H', 'n', 'R', 'r'])

>>> print s.symmetric_difference(['R', 'a', 'n', 'k'])
set(['c', 'e', 'H', 'n', 'R', 'r'])

>>> print s.symmetric_difference(enumerate(['R', 'a', 'n', 'k']))
set(['a', 'c', 'e', 'H', (0, 'R'), 'r', (2, 'n'), 'k', (1, 'a'), (3, 'k')])

>>> print s.symmetric_difference({"Rank":1})
set(['a', 'c', 'e', 'H', 'k', 'Rank', 'r'])

>>> s ^ set("Rank")
set(['c', 'e', 'H', 'n', 'R', 'r'])

=====Problem Statement=====
Students of District College have subscriptions to English and French newspapers. Some students have subscribed to English only, some have subscribed to French only, and some have subscribed to both newspapers.

You are given two sets of student roll numbers. One set has subscribed to the English newspaper, and one set has subscribed to the French newspaper. Your task is to find the total number of students who have subscribed to either the English or the French newspaper but not both.

=====Input Format=====
The first line contains the number of students who have subscribed to the English newspaper.
The second line contains the space separated list of student roll numbers who have subscribed to the English newspaper.
The third line contains the number of students who have subscribed to the French newspaper.
The fourth line contains the space separated list of student roll numbers who have subscribed to the French newspaper.

=====Constraints=====
0 < Total number of students in college < 1000

=====Output Format=====
Output total number of students who have subscriptions to the English or the French newspaper but not both.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Marc loves cupcakes, but he also likes to stay fit. Each cupcake has a calorie count, and Marc can walk a distance to expend those calories.  If Marc has eaten $j$ cupcakes so far, after eating a cupcake with $\textbf{C}$ calories he must walk at least $2^j\times c$  miles to maintain his weight.

Example 

$calorie=[5,10,7]$   

If he eats the cupcakes in the order shown, the miles he will need to walk are $(2^0\times5)+(2^1\times10)+(2^2\times7)=5+20+28=53$.  This is not the minimum, though, so we need to test other orders of consumption.  In this case, our minimum miles is calculated as $(2^0\times10)+(2^1\times7)+(2^2\times5)=10+14+20=44$.

Given the individual calorie counts for each of the cupcakes, determine the minimum number of miles Marc must walk to maintain his weight. Note that he can eat the cupcakes in any order.  

Function Description  

Complete the marcsCakewalk function in the editor below.  

marcsCakewalk has the following parameter(s):  

int calorie[n]: the calorie counts for each cupcake   

Returns   

long: the minimum miles necessary

Input Format

The first line contains an integer $n$, the number of cupcakes in $calorie$. 

The second line contains $n$ space-separated integers, $\text{calorie}[i]$.

Constraints

$1\leq n\leq40$
$1\leq c[i]\leq1000$

Sample Input 0
3
1 3 2

Sample Output 0
11

Explanation 0

Let's say the number of miles Marc must walk to maintain his weight is $miles$. He can minimize $miles$ by eating the $n=3$ cupcakes in the following order: 

Eat the cupcake with $c_1=3$ calories, so $miles=0+(3\cdot2^0)=3$.
Eat the cupcake with $c_2=2$ calories, so $miles=3+(2\cdot2^1)=7$.
Eat the cupcake with $c_{0}=1$ calories, so $miles=7+(1\cdot2^2)=11$.

We then print the final value of $miles$, which is $\mbox{11}$, as our answer.

Sample Input 1
4
7 4 9 6

Sample Output 1
79

Explanation 1

$(2^0*9)+(2^1*7)+(2^2*6)+(2^3*4)=9+14+24+32=79$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A string of length 6 consisting of lowercase English letters is said to be coffee-like if and only if its 3-rd and 4-th characters are equal and its 5-th and 6-th characters are also equal.

Given a string S, determine whether it is coffee-like.

-----Constraints-----
 - S is a string of length 6 consisting of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
If S is coffee-like, print Yes; otherwise, print No.

-----Sample Input-----
sippuu

-----Sample Output-----
Yes

In sippuu, the 3-rd and 4-th characters are equal, and the 5-th and 6-th characters are also equal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently n students from city S moved to city P to attend a programming camp.

They moved there by train. In the evening, all students in the train decided that they want to drink some tea. Of course, no two people can use the same teapot simultaneously, so the students had to form a queue to get their tea.

i-th student comes to the end of the queue at the beginning of l_{i}-th second. If there are multiple students coming to the queue in the same moment, then the student with greater index comes after the student with lesser index. Students in the queue behave as follows: if there is nobody in the queue before the student, then he uses the teapot for exactly one second and leaves the queue with his tea; otherwise the student waits for the people before him to get their tea. If at the beginning of r_{i}-th second student i still cannot get his tea (there is someone before him in the queue), then he leaves the queue without getting any tea. 

For each student determine the second he will use the teapot and get his tea (if he actually gets it).


-----Input-----

The first line contains one integer t — the number of test cases to solve (1 ≤ t ≤ 1000).

Then t test cases follow. The first line of each test case contains one integer n (1 ≤ n ≤ 1000) — the number of students.

Then n lines follow. Each line contains two integer l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ 5000) — the second i-th student comes to the end of the queue, and the second he leaves the queue if he still cannot get his tea.

It is guaranteed that for every $i \in [ 2 ; n ]$ condition l_{i} - 1 ≤ l_{i} holds.

The sum of n over all test cases doesn't exceed 1000.

Note that in hacks you have to set t = 1.


-----Output-----

For each test case print n integers. i-th of them must be equal to the second when i-th student gets his tea, or 0 if he leaves without tea.


-----Example-----
Input
2
2
1 3
1 4
3
1 5
1 1
2 3

Output
1 2 
1 0 2 



-----Note-----

The example contains 2 tests:

  During 1-st second, students 1 and 2 come to the queue, and student 1 gets his tea. Student 2 gets his tea during 2-nd second.  During 1-st second, students 1 and 2 come to the queue, student 1 gets his tea, and student 2 leaves without tea. During 2-nd second, student 3 comes and gets his tea.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: The Fibonacci Segment

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have array *a*1,<=*a*2,<=...,<=*a**n*. Segment [*l*,<=*r*] (1<=≤<=*l*<=≤<=*r*<=≤<=*n*) is good if *a**i*<==<=*a**i*<=-<=1<=+<=*a**i*<=-<=2, for all *i* (*l*<=+<=2<=≤<=*i*<=≤<=*r*).

Let's define *len*([*l*,<=*r*])<==<=*r*<=-<=*l*<=+<=1, *len*([*l*,<=*r*]) is the length of the segment [*l*,<=*r*]. Segment [*l*1,<=*r*1], is longer than segment [*l*2,<=*r*2], if *len*([*l*1,<=*r*1])<=&gt;<=*len*([*l*2,<=*r*2]).

Your task is to find a good segment of the maximum length in array *a*. Note that a segment of length 1 or 2 is always good.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=105) — the number of elements in the array. The second line contains integers: *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=109).

Output Specification:
Print the length of the longest good segment in array *a*.

Demo Input:
['10\n1 2 3 5 8 13 21 34 55 89\n', '5\n1 1 1 1 1\n']

Demo Output:
['10\n', '2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree consising of N vertices. What is the minimum number of vertices that should be removed that all the remaining parts of the initial tree will contain less than K vertices?

Input
The first line contains one integer K.
The second line contains one integer N.
The third line contains N-1 space-separated intgers ai for 2 ≤ i ≤ N which means that vertices i and ai are connected by an edge. 

Output
Output one number - answer for the question.

Constraints
1 ≤ K, N ≤ 10 000
ai < i

SAMPLE INPUT
3
12
1 1 2 2 3 2 3 6 6 6 7

SAMPLE OUTPUT
3

Explanation

We can remove vertices 2, 3, 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A bracket sequence is a string that is one of the following:
 - An empty string;
 - The concatenation of (, A, and ) in this order, for some bracket sequence A ;
 - The concatenation of A and B in this order, for some non-empty bracket sequences A and B /
Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?

-----Constraints-----
 - 1 \leq N \leq 10^6
 - The total length of the strings S_i is at most 10^6.
 - S_i is a non-empty string consisting of ( and ).

-----Input-----
Input is given from Standard Input in the following format:
N
S_1
:
S_N

-----Output-----
If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes; otherwise, print No.

-----Sample Input-----
2
)
(()

-----Sample Output-----
Yes

Concatenating (() and ) in this order forms a bracket sequence.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of a journey in London, UK. The sequence will contain bus **numbers** and TFL tube names as **strings** e.g.

```python
['Northern', 'Central', 243, 1, 'Victoria']
```
Journeys will always only contain a combination of tube names and bus numbers. Each tube journey costs `£2.40` and each bus journey costs `£1.50`. If there are `2` or more adjacent bus journeys, the bus fare is capped for sets of two adjacent buses and calculated as one bus fare for each set.

Your task is to calculate the total cost of the journey and return the cost `rounded to 2 decimal places` in the format (where x is a number): `£x.xx`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ash is on his way to becoming the Pokemon Master. His pokemon can perform the following moves:  
- Tackle - Deal damage worth $X$ points  
- Grow - Increase damage by $Y$ points i.e. $X$ = $X$ + $Y$ 
But, it can only perform Grow first (0 or more times) and then tackle (0 or more) times after which it cannot perform Grow again.

That is, it cannot perform the Grow operation once it has performed the tackle operation.  
A pokemon can be caught only if it’s health is exactly 1. A wild pokemon has appeared and has health worth $H$ points. Find the minimum number of moves required to catch it or say that it is not possible.  

-----Input:-----
- 
The first line of the input consists of a single integer $T$ denoting the number of test cases.
- 
Each test case consists of 3 space-separated integers $H$, $X$ and $Y$.

-----Output:-----
- For each test case, print a single line containing one integer - the minimum number of moves required to catch the pokemon if it is possible to catch it else print -1.

-----Constraints-----
- 
1 <= $T$ <= 103
- 
1 <=  $X$, $Y$ < $H$ <= 109

-----Subtasks-----
Subtask #1 (30 points):
- 1 <=  $X$, $Y$ < $H$ <= 1000
Subtask #2 (70 points):
- Original Constraints

-----Sample Input:-----
2

101 10 10

11 3 3  

-----Sample Output:-----
6

-1  

-----EXPLANATION:-----
- 
Example Case 1:

Ash can make use of Grow once. So $X$ = 10 + 10 = 20

Then he can do Tackle 5 times to decrease $H$ to 1.

OR

Ash can make use of Grow 4 times. So $X$ = 10 + 4*10 = 50

Then he can do Tackle 2 times to decrease $H$ to 1.

Hence, a total of 6 moves are required either way which is minimum.  
- 
Example Case 2:

No matter how many times Ash uses Grow or Tackle, pokemon can never be caught.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Boy Valera likes strings. And even more he likes them, when they are identical. That's why in his spare time Valera plays the following game. He takes any two strings, consisting of lower case Latin letters, and tries to make them identical. According to the game rules, with each move Valera can change one arbitrary character Ai in one of the strings into arbitrary character Bi, but he has to pay for every move a particular sum of money, equal to Wi. He is allowed to make as many moves as he needs. Since Valera is a very economical boy and never wastes his money, he asked you, an experienced programmer, to help him answer the question: what minimum amount of money should Valera have to get identical strings. 

Input

The first input line contains two initial non-empty strings s and t, consisting of lower case Latin letters. The length of each string doesn't exceed 105. The following line contains integer n (0 ≤ n ≤ 500) — amount of possible changings. Then follow n lines, each containing characters Ai and Bi (lower case Latin letters) and integer Wi (0 ≤ Wi ≤ 100), saying that it's allowed to change character Ai into character Bi in any of the strings and spend sum of money Wi.

Output

If the answer exists, output the answer to the problem, and the resulting string. Otherwise output -1 in the only line. If the answer is not unique, output any.

Examples

Input

uayd
uxxd
3
a x 8
x y 13
d c 3


Output

21
uxyd


Input

a
b
3
a b 2
a b 3
b a 5


Output

2
b


Input

abc
ab
6
a b 4
a b 7
b a 8
c b 11
c a 3
a c 0


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.