Typical ICPC Problem

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\le l\le r\le 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.

Giriş verilənləri

The first line of the input contains $2$ integers ($1\le n,m\le 10^6$). The edges of the cactus are given by $m$ edge-simple paths.

The second line of the input contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$, all $a_i$ are distinct), where $a_i$ 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\le k\le 1000$) — the number of nodes on the path. $k$ integers $v_1,v_2,\dots ,v_k$ ($1\le v_i\le n$, $v_i$ are not neccessarily distinct) follow, meaning that there is an edge between nodes $v_i$ and $v_{i+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.

Çıxış verilənləri

Output a single integer — the number of pairs $(l,r)$ ($1\le l\le r\le n)$, such that pair $(l,r)$ is good.

Nümunələr

Qeyd

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)$.