{"raw_statement":[{"iden":"statement","content":"Roman Empire is vast and, as everybody knows, all roads lead to Rome!\n\nFollowing the trail of the Last Centurion, professor Melody Song found an ancient map of Roman roads. The exact position of Rome was forgotten long ago, and Melody wants to recover it from the map. There are $n$ cities on the map, numbered from $1$ to $n$, and $m$ roads. Each road is marked as either _minor_ or _major_. \n\nMajor roads were used to travel to Rome and formed a spanning tree, and minor roads were used as alternatives or to travel between other cities. Each road had some fixed width. It is known that major roads were very wide: if we consider two paths from Rome to any other city, an arbitrary path $P$ and a simple path $Q$ using the major roads, the thinnest road on path $P$ could not be wider than the thinnest road on path $Q$.\n\nThe map found by Melody contains information on every road in Roman Empire, namely its type $t$ and width $w$. Your task is to help her determine which cities may correspond to Rome according to the map.\n\nThe first line of input contains two integers $n$ and $m$ ($1 <= n, m <= 10^5$).\n\nEach of the next $m$ lines contains four integers, $t_i$, $u_i$, $v_i$, and $w_i$, which describe a bidirectional road from city $u_i$ to city $v_i$ with type $t_i$ and width $w_i$ ($1 <= u_i, v_i <= n$, $1 <= w_i <= 10^9$). The type is $t_i = 0$ for minor roads and $t_i = 1$ for major roads.\n\nThere may be multiple roads between the same pair cities, and there may be roads connecting a city to itself. It is guaranteed though that there is exactly one simple path via major roads between each pair of cities.\n\nOn the first line, output an integer $k$ which is number of cities which may be Rome.\n\nOn the second line, output $k$ integers *in ascending order* which are the numbers of those cities.\n\nIt is guaranteed that there is at least one such city.\n\n"},{"iden":"input","content":"The first line of input contains two integers $n$ and $m$ ($1 <= n, m <= 10^5$).Each of the next $m$ lines contains four integers, $t_i$, $u_i$, $v_i$, and $w_i$, which describe a bidirectional road from city $u_i$ to city $v_i$ with type $t_i$ and width $w_i$ ($1 <= u_i, v_i <= n$, $1 <= w_i <= 10^9$). The type is $t_i = 0$ for minor roads and $t_i = 1$ for major roads.There may be multiple roads between the same pair cities, and there may be roads connecting a city to itself. It is guaranteed though that there is exactly one simple path via major roads between each pair of cities."},{"iden":"output","content":"On the first line, output an integer $k$ which is number of cities which may be Rome.On the second line, output $k$ integers *in ascending order* which are the numbers of those cities.It is guaranteed that there is at least one such city."},{"iden":"examples","content":"Input4 6\n1 1 2 2\n1 1 3 2\n1 1 4 2\n0 2 3 3\n0 3 4 3\n0 4 2 3\nOutput1\n1 Input3 3\n0 2 3 1\n1 1 2 2\n1 1 3 2\nOutput3\n1 2 3 "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected multigraph with $ |V| = n $, $ |E| = m $.  \nEach edge $ e \\in E $ has:  \n- a type $ t_e \\in \\{0, 1\\} $ (0 = minor, 1 = major),  \n- a width $ w_e \\in \\mathbb{Z}^+ $, $ 1 \\le w_e \\le 10^9 $.  \n\nLet $ G_M = (V, E_M) $ be the subgraph induced by major roads ($ t_e = 1 $).  \nBy guarantee, $ G_M $ is a spanning tree of $ G $.  \n\nFor any pair of vertices $ u, v \\in V $, let $ P_{u,v} $ denote the unique simple path from $ u $ to $ v $ in $ G_M $.  \nFor any path $ Q $ (not necessarily simple) between $ u $ and $ v $ in $ G $, define:  \n$$\n\\text{minwidth}(Q) = \\min_{e \\in Q} w_e\n$$\n\n**Constraint**  \nFor every vertex $ r \\in V $, and for every other vertex $ v \\in V \\setminus \\{r\\} $:  \nFor every path $ P $ from $ r $ to $ v $ in $ G $,  \n$$\n\\text{minwidth}(P) \\le \\text{minwidth}(P_{r,v})\n$$\n\n**Objective**  \nFind the set $ R \\subseteq V $ of all possible candidates for Rome, i.e., all vertices $ r \\in V $ satisfying the above constraint.  \n\nOutput $ |R| $ and the elements of $ R $ in ascending order.","simple_statement":"You are given a map of n cities and m roads, each road is either major (type 1) or minor (type 0) and has a width. Major roads form a spanning tree. For any city, if it is Rome, then for every other city, the narrowest road on the unique major-road path to Rome must be at least as wide as the narrowest road on any path (using any roads) to that city.\n\nFind all possible cities that could be Rome.","has_page_source":false}