Suppose that you advanced to the ICPC finals. Of course, there will be some cactus problem! To make all participants suffer, even more, it's an edge cactus. As a cherry on top, the input format is unusual. Perfect problem!
You are given an edge cactus on n nodes. Each node contains an integer from 1 to n such that the numbers in the nodes form a permutation. Let's call a pair of numbers (l,r) with 1≤l≤r≤n good, if the following condition holds:
Consider only those nodes, integers on which are in a range [l,r]. Consider only those edges between these nodes, which are present in the original cactus. Then the pair (l,r) is called good if and only if the obtained graph is connected.
Count the number of good pairs.
As a reminder, an edge cactus is a graph such that each edge in it is contained in at most one simple cycle.
As another reminder, a simple cycle is a sequence of distinct nodes (at least 3), such that every two adjacent nodes are connected with an edge, and also the first and the last nodes are connected with an edge.
The first line of the input contains 2 integers (1≤n,m≤106). The edges of the cactus are given by m edge-simple paths.
The second line of the input contains n integers a1,a2,…,an (1≤ai≤n, all ai are distinct), where ai is the number written in the i-th node.
Next m lines contain descriptions of paths, each of which looks as follows:
The first number in a line is an integer k (1≤k≤1000) — the number of nodes on the path. k integers v1,v2,…,vk (1≤vi≤n, vi are not neccessarily distinct) follow, meaning that there is an edge between nodes vi and vi+1 for each i from 1 to k−1. Note that the same node can appear more than once here.
It's guaranteed that each edge will be described at most once and that there are no multi-edges or self-loops.
Output a single integer — the number of pairs (l,r) (1≤l≤r≤n), such that pair (l,r) is good.
In the first sample we have a cactus with edges (1,2) and (2,3). Pairs (1,1),(2,2),(3,3),(1,2),(1,3) are good, while pair (2,3) isn't.
In the second sample we have a cactus with edges (1,2), (2,3), (3,1), (3,4), (4,5), (5,3).