Risk Engineering Merchant Clustering

Each day, some new associations between merchants and a link_type are added, each lasting a given number of days. Associations of the same type that are still active on a day connect the related merchants pairwise. Find the connected components of each day's graph; the pin of a component is the merchant with the highest degree, with ties broken by the lexicographically smallest merchant_id. Output components by size in descending order, then by pin in ascending lexicographic order. After expired associations are removed, components must be recomputed and may split.

输入格式

The first line contains D (always 3). Then the batches for days 1, 2, and 3 are given in order: each batch starts with an integer k, followed by k lines of merchant_id link_type duration. Such a line adds an association on that day that lasts duration days; it is active on days with add_day <= day < add_day + duration. merchant_id and link_type consist of 1..16 ASCII letters, digits, underscores, or hyphens; duration is an integer in 0..3; each batch has at most 100 lines, and there are at most 200 lines in total. Within one batch, (merchant_id, link_type) does not repeat; one merchant may be associated with several types, and one type may be associated with several merchants. Using the batch day number in place of the explicit day field in the upstream tuple is an addition to this site's input protocol.

输出格式

Output three sections, each starting with Day 1, Day 2, or Day 3, followed by one line per connected component: cluster size=<count> pin=<merchant_id>. The graph's vertices are the merchants that have at least one active association that day; a merchant that shares no active link_type with any other merchant forms an isolated component of size 1. Components are sorted by size in descending order, then by pin in ascending lexicographic order; on a day with no active associations, output only the header line. Lines end with LF.

样例 1

输入：

3
0
0
0

输出：

Day 1
Day 2
Day 3

样例 2

输入：

3
5
a email 3
b email 3
c email 3
x phone 3
y phone 3
0
0

输出：

Day 1
  cluster size=3 pin=a
  cluster size=2 pin=x
Day 2
  cluster size=3 pin=a
  cluster size=2 pin=x
Day 3
  cluster size=3 pin=a
  cluster size=2 pin=x

样例 3

输入：

3
1
solo device 3
0
0

输出：

Day 1
  cluster size=1 pin=solo
Day 2
  cluster size=1 pin=solo
Day 3
  cluster size=1 pin=solo

样例 4

输入：

3
2
a shared 1
b shared 1
2
b later 2
c later 2
0

输出：

Day 1
  cluster size=2 pin=a
Day 2
  cluster size=2 pin=b
Day 3
  cluster size=2 pin=b

样例 5

输入：

3
6
a ab 1
b ab 3
b bc 3
c bc 3
c cd 1
d cd 3
0
0

输出：

Day 1
  cluster size=4 pin=b
Day 2
  cluster size=2 pin=b
  cluster size=1 pin=d
Day 3
  cluster size=2 pin=b
  cluster size=1 pin=d

样例 6

输入：

3
4
z left 3
b left 3
a right 3
b right 3
0
0

输出：

Day 1
  cluster size=3 pin=b
Day 2
  cluster size=3 pin=b
Day 3
  cluster size=3 pin=b

样例 7

输入：

3
5
z9 large 3
z1 large 3
z2 large 3
a9 small 3
a1 small 3
0
0

输出：

Day 1
  cluster size=3 pin=z1
  cluster size=2 pin=a1
Day 2
  cluster size=3 pin=z1
  cluster size=2 pin=a1
Day 3
  cluster size=3 pin=z1
  cluster size=2 pin=a1

样例 8

输入：

3
2
a edge 0
b edge 0
2
a edge 2
b edge 2
0

输出：

Day 1
Day 2
  cluster size=2 pin=a
Day 3
  cluster size=2 pin=a

样例说明

The fixed upstream text defines that active relations with the same link_type form edges, a cluster is a connected component, the pin is the merchant with the highest degree with ties going to the smallest ID, and the final order is by size and pin. This site added the batch input, the output text, the limits, and the rule that a merchant with only one active relation whose type is not shared with any other merchant is a singleton.