Maj Gen Khan's troops have been involved in fierce battles
"No permission is required - just open fire on anything that moves," came the order from Maj Gen Tarik Khan, commander of Pakistan's Frontier Corps.
We were sheltering in a traditional mud-walled compound in in the tribal area of Bajaur on the border with Afghanistan.
His men had seized it from militants the day before, after fierce hand-to-hand fighting.
Bursts of fire still rang out and shell cases smoked underfoot as I explored the network of tunnels connecting these compounds, some stretching for several kilometres underground.
The Taleban and al-Qaeda had dug in here over the years, threatening the local tribes and becoming the effective power in the land.
The Pakistani government in the past has been accused of not being committed to the US-led "war on terror" because offensives turned into truces before the job was finished.
But now the new civilian government led by President Asif Ali Zardari - whose wife, Benazir Bhutto, was killed by extremists a year ago - has declared that this time it is a fight to the death.
"If they do not lay down their arms, we will kill them," declared Gen Khan. "There is no other way to bring this to a close."
Pakistan's commitment to the fight against terrorism affects many of us - the majority of serious terror plots in the UK lead back in some way to Pakistan, which has also become a launch pad for the growing insurgency in neighbouring Afghanistan.
"It's a life and death struggle for Pakistan as well as Afghanistan," Brig Gen Mark Milley told me as we flew in a US army helicopter along the Afghan side of the border just a few miles away.
The scenery below was spectacular, rugged and wild, and clearly no barrier to the insurgents.
"The terrain and the culture lends itself to multiple groups, amongst them al-Qaeda, who have established a sanctuary here," explained Gen Milley.
He has lost 16 men to well-trained and motivated insurgents in the past few months alone.
Pakistan is under intense international pressure to destroy the militants who established a safe haven and training camps after fleeing Afghanistan in the wake of the 9/11 attacks in the US.
That pressure has increased following the attacks in Mumbai, which India blames on a Pakistan-based Kashmiri group.
Both generals explained to me that the strategy now is to trap the militants between the hammer of the Pakistani army's offensive in the tribal areas and the anvil of US forces ranged on the other side of the border.
This winter could be decisive in preventing the insurgents retreating back into the tribal areas - but only if the Pakistani army and government hold firm.
But a local Taleban leader who operates from the Pakistan side of the border was defiant.
"Pakistani and Afghan soldiers will die," he said. "We Muslims are not disabled and this war is not going to end."
Jane Corbin comes face-to-face with two would-be suicide bombers.
This man trains many of the suicide bombers sent over the border to Afghanistan to attack coalition troops and Afghan civilians.
In Afghan jails there are 48 would-be suicide bombers from Pakistan.
This year there have been over 140 suicide attacks in Afghanistan - even the streets of the capital, Kabul, are no longer safe.
Abed, a young man we met in one jail, came from the Punjab.
He now repents of what he had done, telling me he was deceived by his Taleban handlers, who sent him to drive a massive truck bomb into what he was told was an army base full of foreigners - British and US troops.
But when he got near he realised the soldiers were speaking the local language.
"I had prayed in my heart that I would not kill any innocent Muslims," he said.
"So when I saw they were Muslims I surrendered myself."
We took a letter from Abed to his family back in Pakistan.
They were horrified to discover what he had become - he had disappeared the year before and they thought he had gone to study at a madrassa, or religious school.
Abed's family were shocked to hear of his fate
But Abed had been recruited by the Taleban and his family were angry and upset.
"The big religious scholars have taken him," said his mother, Naseem, "and we don't know how they persuaded him to do jihad".
His family sent a letter back to Abed telling him they forgave him and asking him to seek forgiveness from God.
In the same jail we met another young bomber, 17-year-old Khalil, who was still filled with hate against foreigners.
He had been caught before he could detonate his suicide vest.
He refused to speak directly to me, a western woman, but told our interpreter that "the Muslims can never be friends with the infidel".
Pakistan needs to root out militancy and terror not only from the tribal areas but from the cities, the religious schools or madrassas and the countryside.
"Yes, it will be a difficult and expensive war to fight," said Rehman Malik, the president's counter-terrorism advisor.
"But we have two options - either we hand Pakistan over to the Taleban or we fight back."
The future security of all of us depends on Pakistan's will and ability to fight back.
Panorama: Britain's Terror Heartland will be broadcast on BBC One at 2030 GMT on Monday 15 December.
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.