Friends or Not

3000ms

262144K

Description:

Polycarpus has a hobby — he develops an unusual social network. His work is almost completed, and there is only one more module to implement — the module which determines friends. Oh yes, in this social network one won't have to add friends manually! Pairs of friends are deduced in the following way. Let's assume that user A sent user B a message at time t₁, and user B sent user A a message at time t₂. If 0 < t₂ - t₁ ≤ d, then user B's message was an answer to user A's one. Users A and B are considered to be friends if A answered at least one B's message or B answered at least one A's message.

You are given the log of messages in chronological order and a number d. Find all pairs of users who will be considered to be friends.

Input:

The first line of the input contains two integers n and d (1 ≤ n, d ≤ 1000). The next n lines contain the messages log. The i-th line contains one line of the log formatted as "A_i B_i t_i" (without the quotes), which means that user A_i sent a message to user B_i at time t_i (1 ≤ i ≤ n). A_i and B_i are non-empty strings at most 20 characters long, consisting of lowercase letters ('a' ... 'z'), and t_i is an integer (0 ≤ t_i ≤ 10000). It is guaranteed that the lines are given in non-decreasing order of t_i's and that no user sent a message to himself. The elements in the lines are separated by single spaces.

Output:

In the first line print integer k — the number of pairs of friends. In the next k lines print pairs of friends as "A_i B_i" (without the quotes). You can print users in pairs and the pairs themselves in any order. Each pair must be printed exactly once.

Sample Input:

4 1
vasya petya 1
petya vasya 2
anya ivan 2
ivan anya 4

Sample Output:

1
petya vasya

Sample Input:

1 1000
a b 0

Sample Output:

Note:

In the first sample test case Vasya and Petya are friends because their messages' sending times are one second apart. Anya and Ivan are not, because their messages' sending times differ by more than one second.

Informação

Provedor Codeforces

Código CF159A